Index: uspace/app/trace/ipcp.c
===================================================================
--- uspace/app/trace/ipcp.c	(revision 1c1da4bb5da22780fc373a9c9faa4e7fdc641791)
+++ uspace/app/trace/ipcp.c	(revision 0ca7286a618557bd1d13cded4ccbe25d62752237)
@@ -38,4 +38,5 @@
 #include <sys/typefmt.h>
 #include <abi/ipc/methods.h>
+#include <macros.h>
 #include "ipc_desc.h"
 #include "proto.h"
@@ -64,6 +65,5 @@
 int have_conn[MAX_PHONE];
 
-#define PCALL_TABLE_CHAINS 32
-hash_table_t pending_calls;
+static hash_table_t pending_calls;
 
 /*
@@ -73,38 +73,45 @@
 proto_t	*proto_unknown;		/**< Protocol with no known methods. */
 
-static hash_index_t pending_call_hash(unsigned long key[]);
-static int pending_call_compare(unsigned long key[], hash_count_t keys,
-    link_t *item);
-static void pending_call_remove_callback(link_t *item);
-
-hash_table_operations_t pending_call_ops = {
+static size_t pending_call_key_hash(unsigned long key[]);
+static size_t pending_call_hash(const link_t *item);
+static bool pending_call_match(unsigned long key[], size_t keys,
+    const link_t *item);
+
+static hash_table_ops_t pending_call_ops = {
 	.hash = pending_call_hash,
-	.compare = pending_call_compare,
-	.remove_callback = pending_call_remove_callback
+	.key_hash = pending_call_key_hash,
+	.match = pending_call_match,
+	.equal = 0,
+	.remove_callback = 0
 };
 
 
-static hash_index_t pending_call_hash(unsigned long key[])
-{
-//	printf("pending_call_hash\n");
-	return key[0] % PCALL_TABLE_CHAINS;
-}
-
-static int pending_call_compare(unsigned long key[], hash_count_t keys,
-    link_t *item)
-{
-	pending_call_t *hs;
-
-//	printf("pending_call_compare\n");
-	hs = hash_table_get_instance(item, pending_call_t, link);
-
-	// FIXME: this will fail if sizeof(long) < sizeof(void *).
-	return key[0] == hs->call_hash;
-}
-
-static void pending_call_remove_callback(link_t *item)
-{
-//	printf("pending_call_remove_callback\n");
-}
+static size_t pending_call_key_hash(unsigned long key[])
+{
+	size_t hash = 17;
+	hash = 31 * hash + key[1];
+	hash = 31 * hash + key[0];
+	return hash;
+}
+
+static size_t pending_call_hash(const link_t *item)
+{
+	pending_call_t *hs = hash_table_get_instance(item, pending_call_t, link);
+	unsigned long key[] = {
+		LOWER32(hs->call_hash),
+		UPPER32(hs->call_hash)
+	};
+	return pending_call_key_hash(key);
+}
+
+static bool pending_call_match(unsigned long key[], size_t keys, 
+	const link_t *item)
+{
+	assert(keys == 2);
+	pending_call_t *hs = hash_table_get_instance(item, pending_call_t, link);
+
+	return MERGE_LOUP32(key[0], key[1]) == hs->call_hash;
+}
+
 
 
@@ -177,5 +184,5 @@
 	}
 
-	hash_table_create(&pending_calls, PCALL_TABLE_CHAINS, 1, &pending_call_ops);
+	hash_table_create(&pending_calls, 0, 2, &pending_call_ops);
 }
 
@@ -190,5 +197,4 @@
 	pending_call_t *pcall;
 	proto_t *proto;
-	unsigned long key[1];
 	oper_t *oper;
 	sysarg_t *args;
@@ -254,7 +260,5 @@
 	pcall->oper = oper;
 
-	key[0] = hash;
-
-	hash_table_insert(&pending_calls, key, &pcall->link);
+	hash_table_insert(&pending_calls, &pcall->link);
 }
 
@@ -336,5 +340,4 @@
 	link_t *item;
 	pending_call_t *pcall;
-	unsigned long key[1];
 	
 	if ((hash & IPC_CALLID_ANSWERED) == 0 && hash != IPCP_CALLID_SYNC) {
@@ -347,5 +350,8 @@
 	
 	hash = hash & ~IPC_CALLID_ANSWERED;
-	key[0] = hash;
+	unsigned long key[] = {
+		LOWER32(hash),
+		UPPER32(hash)
+	};
 	
 	item = hash_table_find(&pending_calls, key);
@@ -358,5 +364,5 @@
 	
 	pcall = hash_table_get_instance(item, pending_call_t, link);
-	hash_table_remove(&pending_calls, key, 1);
+	hash_table_remove(&pending_calls, key, 2);
 	
 	parse_answer(hash, pcall, call);
Index: uspace/app/trace/proto.c
===================================================================
--- uspace/app/trace/proto.c	(revision 1c1da4bb5da22780fc373a9c9faa4e7fdc641791)
+++ uspace/app/trace/proto.c	(revision 0ca7286a618557bd1d13cded4ccbe25d62752237)
@@ -40,8 +40,7 @@
 #include "proto.h"
 
-#define SRV_PROTO_TABLE_CHAINS 32
-#define METHOD_OPER_TABLE_CHAINS 32
-
-hash_table_t srv_proto;
+
+/* Maps service number to protocol */
+static hash_table_t srv_proto;
 
 typedef struct {
@@ -57,96 +56,91 @@
 } method_oper_t;
 
-static hash_index_t srv_proto_hash(unsigned long key[]);
-static int srv_proto_compare(unsigned long key[], hash_count_t keys,
-    link_t *item);
-static void srv_proto_remove_callback(link_t *item);
-
-hash_table_operations_t srv_proto_ops = {
+
+
+
+static size_t srv_proto_key_hash(unsigned long key[])
+{
+	return key[0];
+}
+
+static size_t srv_proto_hash(const link_t *item)
+{
+	srv_proto_t *sp = hash_table_get_instance(item, srv_proto_t, link);
+	unsigned long key = sp->srv;
+	return srv_proto_key_hash(&key);	
+}
+
+static bool srv_proto_match(unsigned long key[], size_t keys, const link_t *item)
+{
+	srv_proto_t *sp = hash_table_get_instance(item, srv_proto_t, link);
+
+	return key[0] == sp->srv;
+}
+
+static hash_table_ops_t srv_proto_ops = {
 	.hash = srv_proto_hash,
-	.compare = srv_proto_compare,
-	.remove_callback = srv_proto_remove_callback
+	.key_hash = srv_proto_key_hash,
+	.match = srv_proto_match,
+	.equal = 0,
+	.remove_callback = 0
 };
 
-static hash_index_t method_oper_hash(unsigned long key[]);
-static int method_oper_compare(unsigned long key[], hash_count_t keys,
-    link_t *item);
-static void method_oper_remove_callback(link_t *item);
-
-hash_table_operations_t method_oper_ops = {
+
+static size_t method_oper_key_hash(unsigned long key[])
+{
+	return key[0];
+}
+
+static size_t method_oper_hash(const link_t *item)
+{
+	method_oper_t *mo = hash_table_get_instance(item, method_oper_t, link);
+	unsigned long key = mo->method;
+	return method_oper_key_hash(&key);
+}
+
+static bool method_oper_match(unsigned long key[], size_t keys, 
+	const link_t *item)
+{
+	method_oper_t *mo = hash_table_get_instance(item, method_oper_t, link);
+
+	return key[0] == mo->method;
+}
+
+static hash_table_ops_t method_oper_ops = {
 	.hash = method_oper_hash,
-	.compare = method_oper_compare,
-	.remove_callback = method_oper_remove_callback
+	.key_hash = method_oper_key_hash,
+	.match = method_oper_match,
+	.equal = 0,
+	.remove_callback = 0
 };
 
-static hash_index_t srv_proto_hash(unsigned long key[])
-{
-	return key[0] % SRV_PROTO_TABLE_CHAINS;
-}
-
-static int srv_proto_compare(unsigned long key[], hash_count_t keys,
-    link_t *item)
+
+void proto_init(void)
+{
+	hash_table_create(&srv_proto, 0, 1, &srv_proto_ops);
+}
+
+void proto_cleanup(void)
+{
+	hash_table_destroy(&srv_proto);
+}
+
+void proto_register(int srv, proto_t *proto)
 {
 	srv_proto_t *sp;
-
-	sp = hash_table_get_instance(item, srv_proto_t, link);
-
-	return key[0] == sp->srv;
-}
-
-static void srv_proto_remove_callback(link_t *item)
-{
-}
-
-static hash_index_t method_oper_hash(unsigned long key[])
-{
-	return key[0] % METHOD_OPER_TABLE_CHAINS;
-}
-
-static int method_oper_compare(unsigned long key[], hash_count_t keys,
-    link_t *item)
-{
-	method_oper_t *mo;
-
-	mo = hash_table_get_instance(item, method_oper_t, link);
-
-	return key[0] == mo->method;
-}
-
-static void method_oper_remove_callback(link_t *item)
-{
-}
-
-
-void proto_init(void)
-{
-	hash_table_create(&srv_proto, SRV_PROTO_TABLE_CHAINS, 1,
-	    &srv_proto_ops);
-}
-
-void proto_cleanup(void)
-{
-	hash_table_destroy(&srv_proto);
-}
-
-void proto_register(int srv, proto_t *proto)
-{
-	srv_proto_t *sp;
-	unsigned long key;
 
 	sp = malloc(sizeof(srv_proto_t));
 	sp->srv = srv;
 	sp->proto = proto;
-	key = srv;
-
-	hash_table_insert(&srv_proto, &key, &sp->link);
+
+	hash_table_insert(&srv_proto, &sp->link);
 }
 
 proto_t *proto_get_by_srv(int srv)
 {
-	unsigned long key;
 	link_t *item;
 	srv_proto_t *sp;
 
-	key = srv;
+	unsigned long key = srv;
 	item = hash_table_find(&srv_proto, &key);
 	if (item == NULL) return NULL;
@@ -159,6 +153,5 @@
 {
 	proto->name = name;
-	hash_table_create(&proto->method_oper, SRV_PROTO_TABLE_CHAINS, 1,
-	    &method_oper_ops);
+	hash_table_create(&proto->method_oper, 0, 1, &method_oper_ops);
 }
 
@@ -181,12 +174,10 @@
 {
 	method_oper_t *mo;
-	unsigned long key;
 
 	mo = malloc(sizeof(method_oper_t));
 	mo->method = method;
 	mo->oper = oper;
-	key = method;
-
-	hash_table_insert(&proto->method_oper, &key, &mo->link);	
+
+	hash_table_insert(&proto->method_oper, &mo->link);	
 }
 
Index: uspace/app/trace/proto.h
===================================================================
--- uspace/app/trace/proto.h	(revision 1c1da4bb5da22780fc373a9c9faa4e7fdc641791)
+++ uspace/app/trace/proto.h	(revision 0ca7286a618557bd1d13cded4ccbe25d62752237)
@@ -62,6 +62,4 @@
 } proto_t;
 
-/* Maps service number to protocol */
-extern hash_table_t srv_proto;
 
 extern void proto_init(void);
Index: uspace/lib/block/libblock.c
===================================================================
--- uspace/lib/block/libblock.c	(revision 1c1da4bb5da22780fc373a9c9faa4e7fdc641791)
+++ uspace/lib/block/libblock.c	(revision 0ca7286a618557bd1d13cded4ccbe25d62752237)
@@ -62,6 +62,4 @@
 static LIST_INITIALIZE(dcl);
 
-#define CACHE_BUCKETS_LOG2  10
-#define CACHE_BUCKETS       (1 << CACHE_BUCKETS_LOG2)
 
 typedef struct {
@@ -256,10 +254,25 @@
 }
 
-static hash_index_t cache_hash(unsigned long *key)
-{
-	return MERGE_LOUP32(key[0], key[1]) & (CACHE_BUCKETS - 1);
-}
-
-static int cache_compare(unsigned long *key, hash_count_t keys, link_t *item)
+static size_t cache_key_hash(unsigned long *key)
+{
+	/* As recommended by Effective Java, 2nd Edition. */
+	size_t hash = 17;
+	hash = 31 * hash + key[1];
+	hash = 31 * hash + key[0];
+	return hash;
+}
+
+static size_t cache_hash(const link_t *item)
+{
+	block_t *b = hash_table_get_instance(item, block_t, hash_link);
+	unsigned long key[] = {
+		LOWER32(b->lba),
+		UPPER32(b->lba)
+	};
+	
+	return cache_key_hash(key);
+}
+
+static bool cache_match(unsigned long *key, size_t keys, const link_t *item)
 {
 	block_t *b = hash_table_get_instance(item, block_t, hash_link);
@@ -267,12 +280,11 @@
 }
 
-static void cache_remove_callback(link_t *item)
-{
-}
-
-static hash_table_operations_t cache_ops = {
+
+static hash_table_ops_t cache_ops = {
 	.hash = cache_hash,
-	.compare = cache_compare,
-	.remove_callback = cache_remove_callback
+	.key_hash = cache_key_hash,
+	.match = cache_match,
+	.equal = 0,
+	.remove_callback = 0
 };
 
@@ -305,6 +317,5 @@
 	cache->blocks_cluster = cache->lblock_size / devcon->pblock_size;
 
-	if (!hash_table_create(&cache->block_hash, CACHE_BUCKETS, 2,
-	    &cache_ops)) {
+	if (!hash_table_create(&cache->block_hash, 0, 2, &cache_ops)) {
 		free(cache);
 		return ENOMEM;
@@ -540,5 +551,5 @@
 		b->lba = ba;
 		b->pba = ba_ltop(devcon, b->lba);
-		hash_table_insert(&cache->block_hash, key, &b->hash_link);
+		hash_table_insert(&cache->block_hash, &b->hash_link);
 
 		/*
Index: uspace/lib/c/generic/adt/hash_table.c
===================================================================
--- uspace/lib/c/generic/adt/hash_table.c	(revision 1c1da4bb5da22780fc373a9c9faa4e7fdc641791)
+++ uspace/lib/c/generic/adt/hash_table.c	(revision 0ca7286a618557bd1d13cded4ccbe25d62752237)
@@ -34,5 +34,15 @@
 
 /*
- * This is an implementation of generic chained hash table.
+ * This is an implementation of a generic resizable chained hash table.
+ * 
+ * The table grows to 2*n+1 buckets each time, starting at n == 89, 
+ * per Thomas Wang's recommendation:
+ * http://www.concentric.net/~Ttwang/tech/hashsize.htm
+ * 
+ * This policy produces prime table sizes for the first five resizes
+ * and generally produces table sizes which are either prime or 
+ * have fairly large (prime/odd) divisors. Having a prime table size
+ * mitigates the use of suboptimal hash functions and distributes
+ * items over the whole table.
  */
 
@@ -44,35 +54,59 @@
 #include <str.h>
 
+/* Optimal initial bucket count. See comment above. */
+#define HT_MIN_BUCKETS  89
+/* The table is resized when the average load per bucket exceeds this number. */
+#define HT_MAX_LOAD     2
+
+
+static size_t round_up_size(size_t size);
+static bool alloc_table(size_t bucket_cnt, list_t **pbuckets);
+static void item_inserted(hash_table_t *h);
+static void item_removed(hash_table_t *h);
+static inline void remove_item(hash_table_t *h, link_t *item);
+static size_t remove_duplicates(hash_table_t *h, unsigned long key[]);
+static size_t remove_matching(hash_table_t *h, unsigned long key[], size_t key_cnt);
+
+/* Dummy do nothing callback to invoke in place of remove_callback == NULL. */
+static void nop_remove_callback(link_t *item)
+{
+	/* no-op */
+}
+
+
 /** Create chained hash table.
  *
  * @param h        Hash table structure. Will be initialized by this call.
- * @param m        Number of hash table buckets.
+ * @param init_size Initial desired number of hash table buckets. Pass zero
+ *                 if you want the default initial size. 
  * @param max_keys Maximal number of keys needed to identify an item.
- * @param op       Hash table operations structure.
+ * @param op       Hash table operations structure. remove_callback()
+ *                 is optional and can be NULL if no action is to be taken
+ *                 upon removal. equal() is optional if and only if
+ *                 hash_table_insert_unique() will never be invoked.
+ *                 All other operations are mandatory. 
  *
  * @return True on success
  *
  */
-bool hash_table_create(hash_table_t *h, hash_count_t m, hash_count_t max_keys,
-    hash_table_operations_t *op)
+bool hash_table_create(hash_table_t *h, size_t init_size, size_t max_keys,
+    hash_table_ops_t *op)
 {
 	assert(h);
-	assert(op && op->hash && op->compare);
+	assert(op && op->hash && op->key_hash && op->match);
 	assert(max_keys > 0);
 	
-	h->entry = malloc(m * sizeof(list_t));
-	if (!h->entry)
+	h->bucket_cnt = round_up_size(init_size);
+	
+	if (!alloc_table(h->bucket_cnt, &h->bucket))
 		return false;
 	
-	memset((void *) h->entry, 0,  m * sizeof(list_t));
-	
-	hash_count_t i;
-	for (i = 0; i < m; i++)
-		list_initialize(&h->entry[i]);
-	
-	h->entries = m;
 	h->max_keys = max_keys;
+	h->items = 0;
 	h->op = op;
 	
+	if (h->op->remove_callback == 0) 
+		h->op->remove_callback = nop_remove_callback;
+	
 	return true;
 }
@@ -84,16 +118,22 @@
 void hash_table_clear(hash_table_t *h)
 {
-	for (hash_count_t chain = 0; chain < h->entries; ++chain) {
-		link_t *cur;
-		link_t *next;
-		
-		for (cur = h->entry[chain].head.next;
-		    cur != &h->entry[chain].head;
-		    cur = next) {
-			next = cur->next;
+	for (size_t idx = 0; idx < h->bucket_cnt; ++idx) {
+		list_foreach_safe(h->bucket[idx], cur, next) {
 			list_remove(cur);
 			h->op->remove_callback(cur);
 		}
 	}
+	
+	h->items = 0;
+
+	/* Shrink the table to its minimum size if possible. */
+	if (HT_MIN_BUCKETS < h->bucket_cnt) {
+		list_t *new_buckets;
+		if (alloc_table(HT_MIN_BUCKETS, &new_buckets)) {
+			free(h->bucket);
+			h->bucket = new_buckets;
+			h->bucket_cnt = HT_MIN_BUCKETS;
+		}
+	}
 }
 
@@ -106,7 +146,10 @@
 {
 	assert(h);
-	assert(h->entry);
-	
-	free(h->entry);
+	assert(h->bucket);
+	
+	free(h->bucket);
+
+	h->bucket = 0;
+	h->bucket_cnt = 0;
 }
 
@@ -117,13 +160,53 @@
  * @param item Item to be inserted into the hash table.
  */
-void hash_table_insert(hash_table_t *h, unsigned long key[], link_t *item)
+void hash_table_insert(hash_table_t *h, link_t *item)
 {
 	assert(item);
-	assert(h && h->op && h->op->hash && h->op->compare);
-	
-	hash_index_t chain = h->op->hash(key);
-	assert(chain < h->entries);
-	
-	list_append(item, &h->entry[chain]);
+	assert(h && h->bucket);
+	assert(h->op && h->op->hash);
+	
+	size_t idx = h->op->hash(item) % h->bucket_cnt;
+	
+	assert(idx < h->bucket_cnt);
+	
+	list_append(item, &h->bucket[idx]);
+	item_inserted(h);
+}
+
+
+/** Insert item into a hash table if not already present.
+ *
+ * @param h    Hash table.
+ * @param key  Array of all keys necessary to compute hash index.
+ * @param item Item to be inserted into the hash table.
+ * 
+ * @return False if such an item had already been inserted. 
+ * @return True if the inserted item was the only item with such a lookup key.
+ */
+bool hash_table_insert_unique(hash_table_t *h, link_t *item)
+{
+	assert(item);
+	assert(h && h->bucket && h->bucket_cnt);
+	assert(h->op && h->op->hash && h->op->equal);
+	
+	size_t item_hash = h->op->hash(item);
+	size_t idx = item_hash % h->bucket_cnt;
+	
+	assert(idx < h->bucket_cnt);
+	
+	/* Check for duplicates. */
+	list_foreach(h->bucket[idx], cur) {
+		/* 
+		 * We could filter out items using their hashes first, but 
+		 * calling equal() might very well be just as fast.
+		 */
+		if (h->op->equal(cur, item))
+			return false;
+	}
+	
+	list_append(item, &h->bucket[idx]);
+	item_inserted(h);
+	
+	return true;
 }
 
@@ -138,19 +221,48 @@
 link_t *hash_table_find(hash_table_t *h, unsigned long key[])
 {
-	assert(h && h->op && h->op->hash && h->op->compare);
-	
-	hash_index_t chain = h->op->hash(key);
-	assert(chain < h->entries);
-	
-	list_foreach(h->entry[chain], cur) {
-		if (h->op->compare(key, h->max_keys, cur)) {
-			/*
-			 * The entry is there.
+	assert(h && h->bucket);
+	assert(h->op && h->op->key_hash && h->op->match);
+	
+	size_t key_hash = h->op->key_hash(key);
+	size_t idx = key_hash % h->bucket_cnt;
+
+	assert(idx < h->bucket_cnt);
+	
+	list_foreach(h->bucket[idx], cur) {
+		/* 
+		 * Is this is the item we are looking for? We could have first 
+		 * checked if the hashes match but op->match() may very well be 
+		 * just as fast as op->hash().
+		 */
+		if (h->op->match(key, h->max_keys, cur)) {
+			return cur;
+		}
+	}
+	
+	return NULL;
+}
+
+
+/** Apply function to all items in hash table.
+ *
+ * @param h   Hash table.
+ * @param f   Function to be applied. Return false if no more items 
+ *            should be visited. The functor must not delete the successor
+ *            of the item passed in the first argument.
+ * @param arg Argument to be passed to the function.
+ *
+ */
+void hash_table_apply(hash_table_t *h, bool (*f)(link_t *, void *), void *arg)
+{	
+	for (size_t idx = 0; idx < h->bucket_cnt; ++idx) {
+		list_foreach_safe(h->bucket[idx], cur, next) {
+			/* 
+			 * The next pointer had already been saved. f() may safely 
+			 * delete cur (but not next!).
 			 */
-			return cur;
-		}
-	}
-	
-	return NULL;
+			if (!f(cur, arg))
+				return;
+		}
+	}
 }
 
@@ -163,76 +275,174 @@
  *             the hash table.
  * @param keys Number of keys in the 'key' array.
- *
- */
-void hash_table_remove(hash_table_t *h, unsigned long key[], hash_count_t keys)
-{
-	assert(h && h->op && h->op->hash && h->op->compare &&
+ * 
+ * @return Returns the number of removed items.
+ */
+size_t hash_table_remove(hash_table_t *h, unsigned long key[], size_t key_cnt)
+{
+	assert(h && h->bucket);
+	assert(h && h->op && h->op->hash &&
 	    h->op->remove_callback);
-	assert(keys <= h->max_keys);
-	
-	if (keys == h->max_keys) {
+	assert(key_cnt <= h->max_keys);
+	
+	/* All keys are known, remove from a specific bucket. */
+	if (key_cnt == h->max_keys) {
+		return remove_duplicates(h, key);
+	} else {
 		/*
-		 * All keys are known, hash_table_find() can be used to find the
-		 * entry.
-		 */
-		
-		link_t *cur = hash_table_find(h, key);
-		if (cur) {
-			list_remove(cur);
-			h->op->remove_callback(cur);
-		}
-		
-		return;
-	}
-	
+		* Fewer keys were passed.
+		* Any partially matching entries are to be removed.
+		*/
+		return remove_matching(h, key, key_cnt);
+	}
+}
+
+/** Removes an item already present in the table. The item must be in the table.*/
+void hash_table_remove_item(hash_table_t *h, link_t *item)
+{
+	assert(item);
+	assert(h && h->bucket);
+	
+	remove_item(h, item);
+}
+
+/** Unlink the item from a bucket, update statistics and resize if needed. */
+static inline void remove_item(hash_table_t *h, link_t *item)
+{
+	assert(item);
+	
+	list_remove(item);
+	item_removed(h);
+	h->op->remove_callback(item);
+}
+
+/** Removes all items matching key in the bucket key hashes to. */
+static size_t remove_duplicates(hash_table_t *h, unsigned long key[])
+{
+	assert(h && h->bucket);
+	assert(h->op && h->op->key_hash && h->op->match);
+	
+	size_t key_hash = h->op->key_hash(key);
+	size_t idx = key_hash % h->bucket_cnt;
+
+	assert(idx < h->bucket_cnt);
+	
+	size_t removed = 0;
+	
+	list_foreach_safe(h->bucket[idx], cur, next) {
+		if (h->op->match(key, h->max_keys, cur)) {
+			++removed;
+			remove_item(h, cur);
+		}
+	}
+	
+	return removed;
+}
+
+/** Removes all items in any bucket in the table that match the partial key. */
+static size_t remove_matching(hash_table_t *h, unsigned long key[], 
+	size_t key_cnt)
+{
+	assert(h && h->bucket);
+	assert(key_cnt < h->max_keys);
+	
+	size_t removed = 0;
 	/*
 	 * Fewer keys were passed.
 	 * Any partially matching entries are to be removed.
 	 */
-	hash_index_t chain;
-	for (chain = 0; chain < h->entries; chain++) {
-		for (link_t *cur = h->entry[chain].head.next;
-		    cur != &h->entry[chain].head;
-		    cur = cur->next) {
-			if (h->op->compare(key, keys, cur)) {
-				link_t *hlp;
-				
-				hlp = cur;
-				cur = cur->prev;
-				
-				list_remove(hlp);
-				h->op->remove_callback(hlp);
-				
-				continue;
+	for (size_t idx = 0; idx < h->bucket_cnt; ++idx) {
+		list_foreach_safe(h->bucket[idx], cur, next) {
+			if (h->op->match(key, key_cnt, cur)) {
+				++removed;
+				remove_item(h, cur);
 			}
 		}
 	}
-}
-
-/** Apply function to all items in hash table.
- *
- * @param h   Hash table.
- * @param f   Function to be applied.
- * @param arg Argument to be passed to the function.
- *
- */
-void hash_table_apply(hash_table_t *h, void (*f)(link_t *, void *), void *arg)
-{	
-	for (hash_index_t bucket = 0; bucket < h->entries; bucket++) {
-		link_t *cur;
-		link_t *next;
-
-		for (cur = h->entry[bucket].head.next; cur != &h->entry[bucket].head;
-		    cur = next) {
-			/*
-			 * The next pointer must be stored prior to the functor
-			 * call to allow using destructor as the functor (the
-			 * free function could overwrite the cur->next pointer).
-			 */
-			next = cur->next;
-			f(cur, arg);
-		}
-	}
-}
+	
+	return removed;
+	
+}
+
+/** Rounds up size to the nearest suitable table size. */
+static size_t round_up_size(size_t size)
+{
+	size_t rounded_size = HT_MIN_BUCKETS;
+	
+	while (rounded_size < size) {
+		rounded_size = 2 * rounded_size + 1;
+	}
+	
+	return rounded_size;
+}
+
+/** Allocates and initializes the desired number of buckets. True if successful.*/
+static bool alloc_table(size_t bucket_cnt, list_t **pbuckets)
+{
+	assert(pbuckets && HT_MIN_BUCKETS <= bucket_cnt);
+		
+	list_t *buckets = malloc(bucket_cnt * sizeof(list_t));
+	if (!buckets)
+		return false;
+	
+	for (size_t i = 0; i < bucket_cnt; i++)
+		list_initialize(&buckets[i]);
+
+	*pbuckets = buckets;
+	return true;
+}
+
+/** Allocates and rehashes items to a new table. Frees the old table. */
+static void resize(hash_table_t *h, size_t new_bucket_cnt) 
+{
+	assert(h && h->bucket);
+	
+	list_t *new_buckets;
+
+	/* Leave the table as is if we cannot resize. */
+	if (!alloc_table(new_bucket_cnt, &new_buckets))
+		return;
+	
+	/* Rehash all the items to the new table. */
+	for (size_t old_idx = 0; old_idx < h->bucket_cnt; ++old_idx) {
+		list_foreach_safe(h->bucket[old_idx], cur, next) {
+			size_t new_idx = h->op->hash(cur) % new_bucket_cnt;
+			list_remove(cur);
+			list_append(cur, &new_buckets[new_idx]);
+		}
+	}
+	
+	free(h->bucket);
+	h->bucket = new_buckets;
+	h->bucket_cnt = new_bucket_cnt;
+}
+
+/** Shrinks the table if needed. */
+static void item_removed(hash_table_t *h)
+{
+	--h->items;
+	
+	if (HT_MIN_BUCKETS < h->items && h->items <= HT_MAX_LOAD * h->bucket_cnt / 4) {
+		/* 
+		 * Keep the bucket_cnt odd (possibly also prime). 
+		 * Shrink from 2n + 1 to n. Integer division discards the +1.
+		 */
+		size_t new_bucket_cnt = h->bucket_cnt / 2;
+		resize(h, new_bucket_cnt);
+	}
+}
+
+/** Grows the table if needed. */
+static void item_inserted(hash_table_t *h)
+{
+	++h->items;
+	
+	/* Grow the table if the average bucket load exceeds the maximum. */
+	if (HT_MAX_LOAD * h->bucket_cnt < h->items) {
+		/* Keep the bucket_cnt odd (possibly also prime). */
+		size_t new_bucket_cnt = 2 * h->bucket_cnt + 1;
+		resize(h, new_bucket_cnt);
+	}
+}
+
 
 /** @}
Index: uspace/lib/c/generic/async.c
===================================================================
--- uspace/lib/c/generic/async.c	(revision 1c1da4bb5da22780fc373a9c9faa4e7fdc641791)
+++ uspace/lib/c/generic/async.c	(revision 0ca7286a618557bd1d13cded4ccbe25d62752237)
@@ -115,6 +115,4 @@
 #include <macros.h>
 
-#define CLIENT_HASH_TABLE_BUCKETS  32
-#define CONN_HASH_TABLE_BUCKETS    32
 
 /** Session data */
@@ -392,12 +390,24 @@
 static LIST_INITIALIZE(timeout_list);
 
-static hash_index_t client_hash(unsigned long key[])
+static size_t client_key_hash(unsigned long key[])
 {
 	assert(key);
-	
-	return (((key[0]) >> 4) % CLIENT_HASH_TABLE_BUCKETS);
-}
-
-static int client_compare(unsigned long key[], hash_count_t keys, link_t *item)
+	/* LOWER32(in_task_id) */
+	return key[0] >> 4;
+}
+
+static size_t client_hash(const link_t *item)
+{
+	client_t *client = hash_table_get_instance(item, client_t, link);
+	
+	unsigned long key[2] = {
+		LOWER32(client->in_task_id),
+		UPPER32(client->in_task_id),
+	};
+
+	return client_key_hash(key);
+}
+
+static bool client_match(unsigned long key[], size_t keys, const link_t *item)
 {
 	assert(key);
@@ -410,13 +420,12 @@
 }
 
-static void client_remove(link_t *item)
-{
-}
 
 /** Operations for the client hash table. */
-static hash_table_operations_t client_hash_table_ops = {
+static hash_table_ops_t client_hash_table_ops = {
 	.hash = client_hash,
-	.compare = client_compare,
-	.remove_callback = client_remove
+	.key_hash = client_key_hash,
+	.match = client_match,
+	.equal = 0,
+	.remove_callback = 0
 };
 
@@ -428,9 +437,15 @@
  *
  */
-static hash_index_t conn_hash(unsigned long key[])
+static size_t conn_key_hash(unsigned long key[])
 {
 	assert(key);
-	
-	return (((key[0]) >> 4) % CONN_HASH_TABLE_BUCKETS);
+	return key[0] >> 4;
+}
+
+static size_t conn_hash(const link_t *item)
+{
+	connection_t *conn = hash_table_get_instance(item, connection_t, link);
+	unsigned long key = conn->in_phone_hash;
+	return conn_key_hash(&key);
 }
 
@@ -444,5 +459,5 @@
  *
  */
-static int conn_compare(unsigned long key[], hash_count_t keys, link_t *item)
+static bool conn_match(unsigned long key[], size_t keys, const link_t *item)
 {
 	assert(key);
@@ -453,4 +468,12 @@
 }
 
+static bool conn_equal(const link_t *item1, const link_t *item2)
+{
+	connection_t *c1 = hash_table_get_instance(item1, connection_t, link);
+	connection_t *c2 = hash_table_get_instance(item2, connection_t, link);
+	
+	return c1->in_phone_hash == c2->in_phone_hash;
+}
+
 static void conn_remove(link_t *item)
 {
@@ -458,7 +481,9 @@
 
 /** Operations for the connection hash table. */
-static hash_table_operations_t conn_hash_table_ops = {
+static hash_table_ops_t conn_hash_table_ops = {
 	.hash = conn_hash,
-	.compare = conn_compare,
+	.key_hash = conn_key_hash,
+	.match = conn_match,
+	.equal = conn_equal,
 	.remove_callback = conn_remove
 };
@@ -715,5 +740,5 @@
 		
 			atomic_set(&client->refcnt, 1);
-			hash_table_insert(&client_hash_table, key, &client->link);
+			hash_table_insert(&client_hash_table, &client->link);
 		}
 	}
@@ -915,8 +940,7 @@
 	
 	/* Add connection to the connection hash table */
-	unsigned long key = conn->in_phone_hash;
 	
 	futex_down(&async_futex);
-	hash_table_insert(&conn_hash_table, &key, &conn->link);
+	hash_table_insert(&conn_hash_table, &conn->link);
 	futex_up(&async_futex);
 	
@@ -1110,10 +1134,8 @@
 void __async_init(void)
 {
-	if (!hash_table_create(&client_hash_table, CLIENT_HASH_TABLE_BUCKETS,
-	    2, &client_hash_table_ops))
+	if (!hash_table_create(&client_hash_table, 0, 2, &client_hash_table_ops))
 		abort();
 	
-	if (!hash_table_create(&conn_hash_table, CONN_HASH_TABLE_BUCKETS,
-	    1, &conn_hash_table_ops))
+	if (!hash_table_create(&conn_hash_table, 0, 1, &conn_hash_table_ops))
 		abort();
 	
Index: uspace/lib/c/include/adt/hash_table.h
===================================================================
--- uspace/lib/c/include/adt/hash_table.h	(revision 1c1da4bb5da22780fc373a9c9faa4e7fdc641791)
+++ uspace/lib/c/include/adt/hash_table.h	(revision 0ca7286a618557bd1d13cded4ccbe25d62752237)
@@ -40,20 +40,16 @@
 #include <bool.h>
 
-typedef unsigned long hash_count_t;
-typedef unsigned long hash_index_t;
 
 /** Set of operations for hash table. */
 typedef struct {
-	/** Hash function.
-	 *
-	 * @param key Array of keys needed to compute hash index.
-	 *            All keys must be passed.
-	 *
-	 * @return Index into hash table.
-	 *
+	/** Returns the hash of the key stored in the item.
 	 */
-	hash_index_t (*hash)(unsigned long key[]);
+	size_t (*hash)(const link_t *item);
 	
-	/** Hash table item comparison function.
+	/** Returns the hash of the key.
+	 */
+	size_t (*key_hash)(unsigned long key[]);
+	
+	/** Hash table item match function.
 	 *
 	 * @param key Array of keys that will be compared with item. It is
@@ -63,20 +59,26 @@
 	 *
 	 */
-	int (*compare)(unsigned long key[], hash_count_t keys, link_t *item);
+	bool (*match)(unsigned long key[], size_t keys, const link_t *item);
+
+	/** 
+	 */
+	bool (*equal)(const link_t *item1, const link_t *item2);
 	
 	/** Hash table item removal callback.
+	 * 
+	 * Must not invoke any mutating functions of the hash table.
 	 *
 	 * @param item Item that was removed from the hash table.
-	 *
 	 */
 	void (*remove_callback)(link_t *item);
-} hash_table_operations_t;
+} hash_table_ops_t;
 
 /** Hash table structure. */
 typedef struct {
-	list_t *entry;
-	hash_count_t entries;
-	hash_count_t max_keys;
-	hash_table_operations_t *op;
+	list_t *bucket;
+	size_t bucket_cnt;
+	size_t max_keys;
+	size_t items;
+	hash_table_ops_t *op;
 } hash_table_t;
 
@@ -84,13 +86,15 @@
     list_get_instance((item), type, member)
 
-extern bool hash_table_create(hash_table_t *, hash_count_t, hash_count_t,
-    hash_table_operations_t *);
+extern bool hash_table_create(hash_table_t *, size_t, size_t, 
+	hash_table_ops_t *);
 extern void hash_table_clear(hash_table_t *);
-extern void hash_table_insert(hash_table_t *, unsigned long [], link_t *);
+extern void hash_table_insert(hash_table_t *, link_t *);
+extern bool hash_table_insert_unique(hash_table_t *, link_t *);
 extern link_t *hash_table_find(hash_table_t *, unsigned long []);
-extern void hash_table_remove(hash_table_t *, unsigned long [], hash_count_t);
+extern size_t hash_table_remove(hash_table_t *, unsigned long [], size_t);
+extern void hash_table_remove_item(hash_table_t *, link_t *);
 extern void hash_table_destroy(hash_table_t *);
-extern void hash_table_apply(hash_table_t *, void (*)(link_t *, void *),
-    void *);
+extern void hash_table_apply(hash_table_t *, bool (*)(link_t *, void *), 
+	void *);
 
 #endif
Index: uspace/lib/c/include/adt/list.h
===================================================================
--- uspace/lib/c/include/adt/list.h	(revision 1c1da4bb5da22780fc373a9c9faa4e7fdc641791)
+++ uspace/lib/c/include/adt/list.h	(revision 0ca7286a618557bd1d13cded4ccbe25d62752237)
@@ -71,4 +71,36 @@
 	    iterator != &(list).head; iterator = iterator->next)
 
+/** Unlike list_foreach(), allows removing items while traversing a list.
+ * 
+ * @code
+ * list_t mylist;
+ * typedef struct item {
+ *     int value;
+ *     link_t item_link;
+ * } item_t;
+ * 
+ * //..
+ * 
+ * // Print each list element's value and remove the element from the list.
+ * list_foreach_safe(mylist, cur_link, next_link) {
+ *     item_t *cur_item = list_get_instance(cur_link, item_t, item_link);
+ *     printf("%d\n", cur_item->value);
+ *     list_remove(cur_link);
+ * }
+ * @endcode
+ * 
+ * @param list List to traverse.
+ * @param iterator Iterator to the current element of the list.
+ *             The item this iterator points may be safely removed
+ *             from the list.
+ * @param next_iter Iterator to the next element of the list.
+ */
+#define list_foreach_safe(list, iterator, next_iter) \
+	for (link_t *iterator = (list).head.next, \
+		*next_iter = iterator->next; \
+		iterator != &(list).head; \
+		iterator = next_iter, next_iter = iterator->next)
+
+
 #define assert_link_not_used(link) \
 	assert(((link)->prev == NULL) && ((link)->next == NULL))
Index: uspace/lib/nic/include/nic_wol_virtues.h
===================================================================
--- uspace/lib/nic/include/nic_wol_virtues.h	(revision 1c1da4bb5da22780fc373a9c9faa4e7fdc641791)
+++ uspace/lib/nic/include/nic_wol_virtues.h	(revision 0ca7286a618557bd1d13cded4ccbe25d62752237)
@@ -51,5 +51,5 @@
 	 * Operations for table
 	 */
-	hash_table_operations_t table_operations;
+	hash_table_ops_t table_operations;
 	/**
 	 * WOL virtues hashed by their ID's.
Index: uspace/lib/nic/src/nic_wol_virtues.c
===================================================================
--- uspace/lib/nic/src/nic_wol_virtues.c	(revision 1c1da4bb5da22780fc373a9c9faa4e7fdc641791)
+++ uspace/lib/nic/src/nic_wol_virtues.c	(revision 0ca7286a618557bd1d13cded4ccbe25d62752237)
@@ -40,11 +40,22 @@
 #include <errno.h>
 
-#define NIC_WV_HASH_COUNT 32
-
-/**
- * Hash table helper function
- */
-static int nic_wv_compare(unsigned long key[], hash_count_t keys,
-	link_t *item)
+
+/*
+ * Hash table helper functions
+ */
+
+static size_t nic_wv_key_hash(unsigned long keys[])
+{
+	return keys[0];
+}
+
+static size_t nic_wv_hash(const link_t *item)
+{
+	nic_wol_virtue_t *virtue = (nic_wol_virtue_t *) item;
+	unsigned long key = virtue->id;
+	return nic_wv_key_hash(&key);
+}
+
+static bool nic_wv_match(unsigned long key[], size_t keys, const link_t *item)
 {
 	nic_wol_virtue_t *virtue = (nic_wol_virtue_t *) item;
@@ -53,19 +64,4 @@
 
 /**
- * Hash table helper function
- */
-static void nic_wv_rc(link_t *item)
-{
-}
-
-/**
- * Hash table helper function
- */
-static hash_index_t nic_wv_hash(unsigned long keys[])
-{
-	return keys[0] % NIC_WV_HASH_COUNT;
-}
-
-/**
  * Initializes the WOL virtues structure
  *
@@ -77,10 +73,12 @@
 int nic_wol_virtues_init(nic_wol_virtues_t *wvs)
 {
-	bzero(wvs, sizeof (nic_wol_virtues_t));
-	wvs->table_operations.compare = nic_wv_compare;
+	bzero(wvs, sizeof(nic_wol_virtues_t));
 	wvs->table_operations.hash = nic_wv_hash;
-	wvs->table_operations.remove_callback = nic_wv_rc;
-	if (!hash_table_create(&wvs->table, NIC_WV_HASH_COUNT, 1,
-		&wvs->table_operations)) {
+	wvs->table_operations.key_hash = nic_wv_key_hash;
+	wvs->table_operations.match = nic_wv_match;
+	wvs->table_operations.equal = 0;
+	wvs->table_operations.remove_callback = 0;
+	
+	if (!hash_table_create(&wvs->table, 0, 1, &wvs->table_operations)) {
 		return ENOMEM;
 	}
@@ -172,6 +170,5 @@
 	} while (NULL !=
 		hash_table_find(&wvs->table, (unsigned long *) &virtue->id));
-	hash_table_insert(&wvs->table,
-		(unsigned long *) &virtue->id, &virtue->item);
+	hash_table_insert(&wvs->table, &virtue->item);
 	virtue->next = wvs->lists[virtue->type];
 	wvs->lists[virtue->type] = virtue;
Index: uspace/srv/devman/devman.c
===================================================================
--- uspace/srv/devman/devman.c	(revision 1c1da4bb5da22780fc373a9c9faa4e7fdc641791)
+++ uspace/srv/devman/devman.c	(revision 0ca7286a618557bd1d13cded4ccbe25d62752237)
@@ -66,11 +66,32 @@
 /* hash table operations */
 
-static hash_index_t devices_hash(unsigned long key[])
-{
-	return key[0] % DEVICE_BUCKETS;
-}
-
-static int devman_devices_compare(unsigned long key[], hash_count_t keys,
-    link_t *item)
+static size_t devices_key_hash(unsigned long key[])
+{
+	return key[0];
+}
+
+static size_t devman_devices_hash(const link_t *item)
+{
+	dev_node_t *dev = hash_table_get_instance(item, dev_node_t, devman_dev);
+	unsigned long key = dev->handle;
+	return devices_key_hash(&key);
+}
+
+static size_t devman_functions_hash(const link_t *item)
+{
+	fun_node_t *fun = hash_table_get_instance(item, fun_node_t, devman_fun);
+	unsigned long key = fun->handle;
+	return devices_key_hash(&key);
+}
+
+static size_t loc_functions_hash(const link_t *item)
+{
+	fun_node_t *fun = hash_table_get_instance(item, fun_node_t, loc_fun);
+	unsigned long key = fun->service_id;
+	return devices_key_hash(&key);
+}
+
+static bool devman_devices_match(unsigned long key[], size_t keys,
+    const link_t *item)
 {
 	dev_node_t *dev = hash_table_get_instance(item, dev_node_t, devman_dev);
@@ -78,6 +99,6 @@
 }
 
-static int devman_functions_compare(unsigned long key[], hash_count_t keys,
-    link_t *item)
+static bool devman_functions_match(unsigned long key[], size_t keys,
+    const link_t *item)
 {
 	fun_node_t *fun = hash_table_get_instance(item, fun_node_t, devman_fun);
@@ -85,6 +106,6 @@
 }
 
-static int loc_functions_compare(unsigned long key[], hash_count_t keys,
-    link_t *item)
+static bool loc_functions_match(unsigned long key[], size_t keys,
+    const link_t *item)
 {
 	fun_node_t *fun = hash_table_get_instance(item, fun_node_t, loc_fun);
@@ -92,24 +113,27 @@
 }
 
-static void devices_remove_callback(link_t *item)
-{
-}
-
-static hash_table_operations_t devman_devices_ops = {
-	.hash = devices_hash,
-	.compare = devman_devices_compare,
-	.remove_callback = devices_remove_callback
+
+static hash_table_ops_t devman_devices_ops = {
+	.hash = devman_devices_hash,
+	.key_hash = devices_key_hash,
+	.match = devman_devices_match,
+	.equal = 0,
+	.remove_callback = 0
 };
 
-static hash_table_operations_t devman_functions_ops = {
-	.hash = devices_hash,
-	.compare = devman_functions_compare,
-	.remove_callback = devices_remove_callback
+static hash_table_ops_t devman_functions_ops = {
+	.hash = devman_functions_hash,
+	.key_hash = devices_key_hash,
+	.match = devman_functions_match,
+	.equal = 0,
+	.remove_callback = 0
 };
 
-static hash_table_operations_t loc_devices_ops = {
-	.hash = devices_hash,
-	.compare = loc_functions_compare,
-	.remove_callback = devices_remove_callback
+static hash_table_ops_t loc_devices_ops = {
+	.hash = loc_functions_hash,
+	.key_hash = devices_key_hash,
+	.match = loc_functions_match,
+	.equal = 0,
+	.remove_callback = 0
 };
 
@@ -974,10 +998,7 @@
 	tree->current_handle = 0;
 	
-	hash_table_create(&tree->devman_devices, DEVICE_BUCKETS, 1,
-	    &devman_devices_ops);
-	hash_table_create(&tree->devman_functions, DEVICE_BUCKETS, 1,
-	    &devman_functions_ops);
-	hash_table_create(&tree->loc_functions, DEVICE_BUCKETS, 1,
-	    &loc_devices_ops);
+	hash_table_create(&tree->devman_devices, 0, 1, &devman_devices_ops);
+	hash_table_create(&tree->devman_functions, 0, 1, &devman_functions_ops);
+	hash_table_create(&tree->loc_functions, 0, 1, &loc_devices_ops);
 	
 	fibril_rwlock_initialize(&tree->rwlock);
@@ -1282,6 +1303,5 @@
 	/* Add the node to the handle-to-node map. */
 	dev->handle = ++tree->current_handle;
-	unsigned long key = dev->handle;
-	hash_table_insert(&tree->devman_devices, &key, &dev->devman_dev);
+	hash_table_insert(&tree->devman_devices, &dev->devman_dev);
 
 	/* Add the node to the list of its parent's children. */
@@ -1346,6 +1366,5 @@
 	/* Add the node to the handle-to-node map. */
 	fun->handle = ++tree->current_handle;
-	unsigned long key = fun->handle;
-	hash_table_insert(&tree->devman_functions, &key, &fun->devman_fun);
+	hash_table_insert(&tree->devman_functions, &fun->devman_fun);
 
 	/* Add the node to the list of its parent's children. */
@@ -1499,6 +1518,5 @@
 	assert(fibril_rwlock_is_write_locked(&tree->rwlock));
 	
-	unsigned long key = (unsigned long) fun->service_id;
-	hash_table_insert(&tree->loc_functions, &key, &fun->loc_fun);
+	hash_table_insert(&tree->loc_functions, &fun->loc_fun);
 }
 
Index: uspace/srv/devman/devman.h
===================================================================
--- uspace/srv/devman/devman.h	(revision 1c1da4bb5da22780fc373a9c9faa4e7fdc641791)
+++ uspace/srv/devman/devman.h	(revision 0ca7286a618557bd1d13cded4ccbe25d62752237)
@@ -52,5 +52,4 @@
 
 #define MATCH_EXT ".ma"
-#define DEVICE_BUCKETS 256
 
 #define LOC_DEVICE_NAMESPACE "devices"
Index: uspace/srv/fs/cdfs/cdfs_ops.c
===================================================================
--- uspace/srv/fs/cdfs/cdfs_ops.c	(revision 1c1da4bb5da22780fc373a9c9faa4e7fdc641791)
+++ uspace/srv/fs/cdfs/cdfs_ops.c	(revision 0ca7286a618557bd1d13cded4ccbe25d62752237)
@@ -63,6 +63,4 @@
 #define NODE_CACHE_SIZE  200
 
-#define NODES_BUCKETS  256
-
 #define NODES_KEY_SRVC   0
 #define NODES_KEY_INDEX  1
@@ -226,31 +224,45 @@
 static hash_table_t nodes;
 
-static hash_index_t nodes_hash(unsigned long key[])
-{
-	return key[NODES_KEY_INDEX] % NODES_BUCKETS;
-}
-
-static int nodes_compare(unsigned long key[], hash_count_t keys, link_t *item)
-{
-	cdfs_node_t *node =
-	    hash_table_get_instance(item, cdfs_node_t, nh_link);
-	
-	switch (keys) {
-	case 1:
+static size_t nodes_key_hash(unsigned long key[])
+{
+	return key[NODES_KEY_INDEX];
+}
+
+static size_t nodes_hash(const link_t *item)
+{
+	cdfs_node_t *node = hash_table_get_instance(item, cdfs_node_t, nh_link);
+	
+	unsigned long key[] = {
+		[NODES_KEY_INDEX] = node->index
+	};
+	
+	return nodes_key_hash(key);
+}
+
+static bool nodes_match(unsigned long key[], size_t keys, const link_t *item)
+{
+	cdfs_node_t *node = hash_table_get_instance(item, cdfs_node_t, nh_link);
+	
+	if (keys == 1) {
 		return (node->service_id == key[NODES_KEY_SRVC]);
-	case 2:
+	} else {
+		assert(keys == 2);
 		return ((node->service_id == key[NODES_KEY_SRVC]) &&
 		    (node->index == key[NODES_KEY_INDEX]));
-	default:
-		assert((keys == 1) || (keys == 2));
-	}
-	
-	return 0;
+	}
+}
+
+static bool nodes_equal(const link_t *item1, const link_t *item2)
+{
+	cdfs_node_t *node1 = hash_table_get_instance(item1, cdfs_node_t, nh_link);
+	cdfs_node_t *node2 = hash_table_get_instance(item2, cdfs_node_t, nh_link);
+	
+	return node1->service_id == node2->service_id 
+		&& node1->index == node2->index;
 }
 
 static void nodes_remove_callback(link_t *item)
 {
-	cdfs_node_t *node =
-	    hash_table_get_instance(item, cdfs_node_t, nh_link);
+	cdfs_node_t *node = hash_table_get_instance(item, cdfs_node_t, nh_link);
 	
 	assert(node->type == CDFS_DIRECTORY);
@@ -268,7 +280,9 @@
 
 /** Nodes hash table operations */
-static hash_table_operations_t nodes_ops = {
+static hash_table_ops_t nodes_ops = {
 	.hash = nodes_hash,
-	.compare = nodes_compare,
+	.key_hash = nodes_key_hash,
+	.match = nodes_match,
+	.equal = nodes_equal,
 	.remove_callback = nodes_remove_callback
 };
@@ -353,10 +367,5 @@
 	
 	/* Insert the new node into the nodes hash table. */
-	unsigned long key[] = {
-		[NODES_KEY_SRVC] = node->service_id,
-		[NODES_KEY_INDEX] = node->index
-	};
-	
-	hash_table_insert(&nodes, key, &node->nh_link);
+	hash_table_insert(&nodes, &node->nh_link);
 	
 	*rfn = FS_NODE(node);
@@ -912,34 +921,31 @@
 }
 
+static bool cache_remove_closed(link_t *item, void *arg)
+{
+	size_t *premove_cnt = (size_t*)arg;
+	
+	/* Some nodes were requested to be removed from the cache. */
+	if (0 < *premove_cnt) {
+		cdfs_node_t *node =	hash_table_get_instance(item, cdfs_node_t, nh_link);
+
+		if (!node->opened) {
+			hash_table_remove_item(&nodes, item);
+			
+			--nodes_cached;
+			--*premove_cnt;
+		}
+	}
+	
+	/* Only continue if more nodes were requested to be removed. */
+	return 0 < *premove_cnt;
+}
+
 static void cleanup_cache(service_id_t service_id)
 {
 	if (nodes_cached > NODE_CACHE_SIZE) {
-		size_t remove = nodes_cached - NODE_CACHE_SIZE;
-		
-		// FIXME: this accesses the internals of the hash table
-		//        and should be rewritten in a clean way
-		
-		for (hash_index_t chain = 0; chain < nodes.entries; chain++) {
-			for (link_t *link = nodes.entry[chain].head.next;
-			    link != &nodes.entry[chain].head;
-			    link = link->next) {
-				if (remove == 0)
-					return;
-				
-				cdfs_node_t *node =
-				    hash_table_get_instance(link, cdfs_node_t, nh_link);
-				if (node->opened == 0) {
-					link_t *tmp = link;
-					link = link->prev;
-					
-					list_remove(tmp);
-					nodes.op->remove_callback(tmp);
-					nodes_cached--;
-					remove--;
-					
-					continue;
-				}
-			}
-		}
+		size_t remove_cnt = nodes_cached - NODE_CACHE_SIZE;
+		
+		if (0 < remove_cnt)
+			hash_table_apply(&nodes, cache_remove_closed, &remove_cnt);
 	}
 }
@@ -1007,5 +1013,5 @@
 bool cdfs_init(void)
 {
-	if (!hash_table_create(&nodes, NODES_BUCKETS, 2, &nodes_ops))
+	if (!hash_table_create(&nodes, 0, 2, &nodes_ops))
 		return false;
 	
Index: uspace/srv/fs/exfat/exfat_idx.c
===================================================================
--- uspace/srv/fs/exfat/exfat_idx.c	(revision 1c1da4bb5da22780fc373a9c9faa4e7fdc641791)
+++ uspace/srv/fs/exfat/exfat_idx.c	(revision 0ca7286a618557bd1d13cded4ccbe25d62752237)
@@ -112,40 +112,34 @@
 static hash_table_t up_hash;
 
-#define UPH_BUCKETS_LOG	12
-#define UPH_BUCKETS	(1 << UPH_BUCKETS_LOG)
-
 #define UPH_SID_KEY	0
 #define UPH_PFC_KEY	1
 #define UPH_PDI_KEY	2
 
-static hash_index_t pos_hash(unsigned long key[])
-{
-	service_id_t service_id = (service_id_t)key[UPH_SID_KEY];
-	exfat_cluster_t pfc = (exfat_cluster_t)key[UPH_PFC_KEY];
-	unsigned pdi = (unsigned)key[UPH_PDI_KEY];
-
-	hash_index_t h;
-
-	/*
-	 * The least significant half of all bits are the least significant bits
-	 * of the parent node's first cluster.
-	 *
-	 * The least significant half of the most significant half of all bits
-	 * are the least significant bits of the node's dentry index within the
-	 * parent directory node.
-	 *
-	 * The most significant half of the most significant half of all bits
-	 * are the least significant bits of the device handle.
-	 */
-	h = pfc & ((1 << (UPH_BUCKETS_LOG / 2)) - 1);
-	h |= (pdi & ((1 << (UPH_BUCKETS_LOG / 4)) - 1)) <<
-	    (UPH_BUCKETS_LOG / 2); 
-	h |= (service_id & ((1 << (UPH_BUCKETS_LOG / 4)) - 1)) <<
-	    (3 * (UPH_BUCKETS_LOG / 4));
-
-	return h;
-}
-
-static int pos_compare(unsigned long key[], hash_count_t keys, link_t *item)
+static size_t pos_key_hash(unsigned long key[])
+{
+	/* Inspired by Effective Java, 2nd edition. */
+	size_t hash = 17;
+	
+	hash = 31 * hash + key[UPH_PFC_KEY];
+	hash = 31 * hash + key[UPH_PDI_KEY];
+	hash = 31 * hash + key[UPH_SID_KEY];
+	
+	return hash;
+}
+
+static size_t pos_hash(const link_t *item)
+{
+	exfat_idx_t *fidx = list_get_instance(item, exfat_idx_t, uph_link);
+	
+	unsigned long pkey[] = {
+		[UPH_SID_KEY] = fidx->service_id,
+		[UPH_PFC_KEY] = fidx->pfc,
+		[UPH_PDI_KEY] = fidx->pdi,
+	};
+	
+	return pos_key_hash(pkey);
+}
+
+static bool pos_match(unsigned long key[], size_t keys, const link_t *item)
 {
 	service_id_t service_id = (service_id_t)key[UPH_SID_KEY];
@@ -169,13 +163,10 @@
 }
 
-static void pos_remove_callback(link_t *item)
-{
-	/* nothing to do */
-}
-
-static hash_table_operations_t uph_ops = {
+static hash_table_ops_t uph_ops = {
 	.hash = pos_hash,
-	.compare = pos_compare,
-	.remove_callback = pos_remove_callback,
+	.key_hash = pos_key_hash,
+	.match = pos_match,
+	.equal = 0,
+	.remove_callback = 0,
 };
 
@@ -186,25 +177,35 @@
 static hash_table_t ui_hash;
 
-#define UIH_BUCKETS_LOG	12
-#define UIH_BUCKETS	(1 << UIH_BUCKETS_LOG)
-
 #define UIH_SID_KEY	0
 #define UIH_INDEX_KEY	1
 
-static hash_index_t idx_hash(unsigned long key[])
+static size_t idx_key_hash(unsigned long key[])
 {
 	service_id_t service_id = (service_id_t)key[UIH_SID_KEY];
 	fs_index_t index = (fs_index_t)key[UIH_INDEX_KEY];
 
-	hash_index_t h;
-
-	h = service_id & ((1 << (UIH_BUCKETS_LOG / 2)) - 1);
-	h |= (index & ((1 << (UIH_BUCKETS_LOG / 2)) - 1)) <<
-	    (UIH_BUCKETS_LOG / 2);
-
-	return h;
-}
-
-static int idx_compare(unsigned long key[], hash_count_t keys, link_t *item)
+	/* 
+	 * Compute a simple hash unlimited by specific table size as per: 
+	 * Effective Java, 2nd edition.
+	 */
+	size_t hash = 17;
+	hash = 31 * hash + (size_t)service_id;
+	hash = 31 * hash + (size_t)index;
+	return hash;
+}
+
+static size_t idx_hash(const link_t *item)
+{
+	exfat_idx_t *fidx = list_get_instance(item, exfat_idx_t, uih_link);
+	
+	unsigned long ikey[] = {
+		[UIH_SID_KEY] = fidx->service_id,
+		[UIH_INDEX_KEY] = fidx->index,
+	};
+
+	return idx_key_hash(ikey);
+}
+
+static bool idx_match(unsigned long key[], size_t keys, const link_t *item)
 {
 	service_id_t service_id = (service_id_t)key[UIH_SID_KEY];
@@ -233,7 +234,9 @@
 }
 
-static hash_table_operations_t uih_ops = {
+static hash_table_ops_t uih_ops = {
 	.hash = idx_hash,
-	.compare = idx_compare,
+	.key_hash = idx_key_hash,
+	.match = idx_match,
+	.equal = 0,
 	.remove_callback = idx_remove_callback,
 };
@@ -400,10 +403,5 @@
 	}
 		
-	unsigned long ikey[] = {
-		[UIH_SID_KEY] = service_id,
-		[UIH_INDEX_KEY] = fidx->index,
-	};
-	
-	hash_table_insert(&ui_hash, ikey, &fidx->uih_link);
+	hash_table_insert(&ui_hash, &fidx->uih_link);
 	fibril_mutex_lock(&fidx->lock);
 	fibril_mutex_unlock(&used_lock);
@@ -437,14 +435,9 @@
 		}
 		
-		unsigned long ikey[] = {
-			[UIH_SID_KEY] = service_id,
-			[UIH_INDEX_KEY] = fidx->index,
-		};
-	
 		fidx->pfc = pfc;
 		fidx->pdi = pdi;
 
-		hash_table_insert(&up_hash, pkey, &fidx->uph_link);
-		hash_table_insert(&ui_hash, ikey, &fidx->uih_link);
+		hash_table_insert(&up_hash, &fidx->uph_link);
+		hash_table_insert(&ui_hash, &fidx->uih_link);
 	}
 	fibril_mutex_lock(&fidx->lock);
@@ -456,12 +449,6 @@
 void exfat_idx_hashin(exfat_idx_t *idx)
 {
-	unsigned long pkey[] = {
-		[UPH_SID_KEY] = idx->service_id,
-		[UPH_PFC_KEY] = idx->pfc,
-		[UPH_PDI_KEY] = idx->pdi,
-	};
-
-	fibril_mutex_lock(&used_lock);
-	hash_table_insert(&up_hash, pkey, &idx->uph_link);
+	fibril_mutex_lock(&used_lock);
+	hash_table_insert(&up_hash, &idx->uph_link);
 	fibril_mutex_unlock(&used_lock);
 }
@@ -532,7 +519,7 @@
 int exfat_idx_init(void)
 {
-	if (!hash_table_create(&up_hash, UPH_BUCKETS, 3, &uph_ops)) 
+	if (!hash_table_create(&up_hash, 0, 3, &uph_ops)) 
 		return ENOMEM;
-	if (!hash_table_create(&ui_hash, UIH_BUCKETS, 2, &uih_ops)) {
+	if (!hash_table_create(&ui_hash, 0, 2, &uih_ops)) {
 		hash_table_destroy(&up_hash);
 		return ENOMEM;
Index: uspace/srv/fs/ext2fs/ext2fs_ops.c
===================================================================
--- uspace/srv/fs/ext2fs/ext2fs_ops.c	(revision 1c1da4bb5da22780fc373a9c9faa4e7fdc641791)
+++ uspace/srv/fs/ext2fs/ext2fs_ops.c	(revision 0ca7286a618557bd1d13cded4ccbe25d62752237)
@@ -65,5 +65,4 @@
 #define OPEN_NODES_DEV_HANDLE_KEY 0
 #define OPEN_NODES_INODE_KEY 1
-#define OPEN_NODES_BUCKETS 256
 
 typedef struct ext2fs_instance {
@@ -123,12 +122,30 @@
 
 /* Hash table interface for open nodes hash table */
-static hash_index_t open_nodes_hash(unsigned long key[])
-{
-	/* TODO: This is very simple and probably can be improved */
-	return key[OPEN_NODES_INODE_KEY] % OPEN_NODES_BUCKETS;
-}
-
-static int open_nodes_compare(unsigned long key[], hash_count_t keys, 
-    link_t *item)
+static size_t open_nodes_key_hash(unsigned long key[])
+{
+	/* Hash construction recommended in Effective Java, 2nd Edition. */
+	size_t hash = 17;
+	hash = 31 * hash + key[OPEN_NODES_DEV_HANDLE_KEY];
+	hash = 31 * hash + key[OPEN_NODES_INODE_KEY];
+	return hash;
+}
+
+static size_t open_nodes_hash(const link_t *item)
+{
+	ext2fs_node_t *enode = hash_table_get_instance(item, ext2fs_node_t, link);
+
+	assert(enode->instance);
+	assert(enode->inode_ref);
+	
+	unsigned long key[] = {
+		[OPEN_NODES_DEV_HANDLE_KEY] = enode->instance->service_id,
+		[OPEN_NODES_INODE_KEY] = enode->inode_ref->index,
+	};
+	
+	return open_nodes_key_hash(key);
+}
+
+static bool open_nodes_match(unsigned long key[], size_t keys, 
+    const link_t *item)
 {
 	ext2fs_node_t *enode = hash_table_get_instance(item, ext2fs_node_t, link);
@@ -145,13 +162,10 @@
 }
 
-static void open_nodes_remove_cb(link_t *link)
-{
-	/* We don't use remove callback for this hash table */
-}
-
-static hash_table_operations_t open_nodes_ops = {
+static hash_table_ops_t open_nodes_ops = {
 	.hash = open_nodes_hash,
-	.compare = open_nodes_compare,
-	.remove_callback = open_nodes_remove_cb,
+	.key_hash = open_nodes_key_hash,
+	.match = open_nodes_match,
+	.equal = 0,
+	.remove_callback = 0,
 };
 
@@ -161,6 +175,5 @@
 int ext2fs_global_init(void)
 {
-	if (!hash_table_create(&open_nodes, OPEN_NODES_BUCKETS,
-	    OPEN_NODES_KEYS, &open_nodes_ops)) {
+	if (!hash_table_create(&open_nodes, 0, OPEN_NODES_KEYS, &open_nodes_ops)) {
 		return ENOMEM;
 	}
@@ -362,5 +375,5 @@
 	*rfn = node;
 	
-	hash_table_insert(&open_nodes, key, &enode->link);
+	hash_table_insert(&open_nodes, &enode->link);
 	inst->open_nodes_count++;
 	
Index: uspace/srv/fs/fat/fat_idx.c
===================================================================
--- uspace/srv/fs/fat/fat_idx.c	(revision 1c1da4bb5da22780fc373a9c9faa4e7fdc641791)
+++ uspace/srv/fs/fat/fat_idx.c	(revision 0ca7286a618557bd1d13cded4ccbe25d62752237)
@@ -46,4 +46,5 @@
 #include <malloc.h>
 
+
 /** Each instance of this type describes one interval of freed VFS indices. */
 typedef struct {
@@ -113,40 +114,34 @@
 static hash_table_t up_hash;
 
-#define UPH_BUCKETS_LOG	12
-#define UPH_BUCKETS	(1 << UPH_BUCKETS_LOG)
-
 #define UPH_SID_KEY	0
 #define UPH_PFC_KEY	1
 #define UPH_PDI_KEY	2
 
-static hash_index_t pos_hash(unsigned long key[])
-{
-	service_id_t service_id = (service_id_t)key[UPH_SID_KEY];
-	fat_cluster_t pfc = (fat_cluster_t)key[UPH_PFC_KEY];
-	unsigned pdi = (unsigned)key[UPH_PDI_KEY];
-
-	hash_index_t h;
-
-	/*
-	 * The least significant half of all bits are the least significant bits
-	 * of the parent node's first cluster.
-	 *
-	 * The least significant half of the most significant half of all bits
-	 * are the least significant bits of the node's dentry index within the
-	 * parent directory node.
-	 *
-	 * The most significant half of the most significant half of all bits
-	 * are the least significant bits of the device handle.
-	 */
-	h = pfc & ((1 << (UPH_BUCKETS_LOG / 2)) - 1);
-	h |= (pdi & ((1 << (UPH_BUCKETS_LOG / 4)) - 1)) <<
-	    (UPH_BUCKETS_LOG / 2); 
-	h |= (service_id & ((1 << (UPH_BUCKETS_LOG / 4)) - 1)) <<
-	    (3 * (UPH_BUCKETS_LOG / 4));
-
-	return h;
-}
-
-static int pos_compare(unsigned long key[], hash_count_t keys, link_t *item)
+static size_t pos_key_hash(unsigned long key[])
+{
+	/* Inspired by Effective Java, 2nd edition. */
+	size_t hash = 17;
+	
+	hash = 31 * hash + key[UPH_PFC_KEY];
+	hash = 31 * hash + key[UPH_PDI_KEY];
+	hash = 31 * hash + key[UPH_SID_KEY];
+	
+	return hash;
+}
+
+static size_t pos_hash(const link_t *item)
+{
+	fat_idx_t *fidx = list_get_instance(item, fat_idx_t, uph_link);
+	
+	unsigned long pkey[] = {
+		[UPH_SID_KEY] = fidx->service_id,
+		[UPH_PFC_KEY] = fidx->pfc,
+		[UPH_PDI_KEY] = fidx->pdi,
+	};
+	
+	return pos_key_hash(pkey);
+}
+
+static bool pos_match(unsigned long key[], size_t keys, const link_t *item)
 {
 	service_id_t service_id = (service_id_t)key[UPH_SID_KEY];
@@ -170,13 +165,10 @@
 }
 
-static void pos_remove_callback(link_t *item)
-{
-	/* nothing to do */
-}
-
-static hash_table_operations_t uph_ops = {
+static hash_table_ops_t uph_ops = {
 	.hash = pos_hash,
-	.compare = pos_compare,
-	.remove_callback = pos_remove_callback,
+	.key_hash = pos_key_hash,
+	.match = pos_match,
+	.equal = 0,
+	.remove_callback = 0,
 };
 
@@ -187,25 +179,32 @@
 static hash_table_t ui_hash;
 
-#define UIH_BUCKETS_LOG	12
-#define UIH_BUCKETS	(1 << UIH_BUCKETS_LOG)
-
 #define UIH_SID_KEY	0
 #define UIH_INDEX_KEY	1
 
-static hash_index_t idx_hash(unsigned long key[])
-{
-	service_id_t service_id = (service_id_t)key[UIH_SID_KEY];
-	fs_index_t index = (fs_index_t)key[UIH_INDEX_KEY];
-
-	hash_index_t h;
-
-	h = service_id & ((1 << (UIH_BUCKETS_LOG / 2)) - 1);
-	h |= (index & ((1 << (UIH_BUCKETS_LOG / 2)) - 1)) <<
-	    (UIH_BUCKETS_LOG / 2);
-
-	return h;
-}
-
-static int idx_compare(unsigned long key[], hash_count_t keys, link_t *item)
+static size_t idx_key_hash(unsigned long key[])
+{
+	/* 
+	 * Compute a simple hash unlimited by specific table size as per: 
+	 * Effective Java, 2nd edition.
+	 */
+	size_t hash = 17;
+	hash = 31 * hash + key[UIH_SID_KEY];
+	hash = 31 * hash + key[UIH_INDEX_KEY];
+	return hash;
+}
+
+static size_t idx_hash(const link_t *item)
+{
+	fat_idx_t *fidx = list_get_instance(item, fat_idx_t, uih_link);
+	
+	unsigned long ikey[] = {
+		[UIH_SID_KEY] = fidx->service_id,
+		[UIH_INDEX_KEY] = fidx->index,
+	};
+
+	return idx_key_hash(ikey);
+}
+
+static bool idx_match(unsigned long key[], size_t keys, const link_t *item)
 {
 	service_id_t service_id = (service_id_t)key[UIH_SID_KEY];
@@ -234,7 +233,9 @@
 }
 
-static hash_table_operations_t uih_ops = {
+static hash_table_ops_t uih_ops = {
 	.hash = idx_hash,
-	.compare = idx_compare,
+	.key_hash = idx_key_hash,
+	.match = idx_match,
+	.equal = 0,
 	.remove_callback = idx_remove_callback,
 };
@@ -401,10 +402,5 @@
 	}
 		
-	unsigned long ikey[] = {
-		[UIH_SID_KEY] = service_id,
-		[UIH_INDEX_KEY] = fidx->index,
-	};
-	
-	hash_table_insert(&ui_hash, ikey, &fidx->uih_link);
+	hash_table_insert(&ui_hash, &fidx->uih_link);
 	fibril_mutex_lock(&fidx->lock);
 	fibril_mutex_unlock(&used_lock);
@@ -438,14 +434,9 @@
 		}
 		
-		unsigned long ikey[] = {
-			[UIH_SID_KEY] = service_id,
-			[UIH_INDEX_KEY] = fidx->index,
-		};
-	
 		fidx->pfc = pfc;
 		fidx->pdi = pdi;
 
-		hash_table_insert(&up_hash, pkey, &fidx->uph_link);
-		hash_table_insert(&ui_hash, ikey, &fidx->uih_link);
+		hash_table_insert(&up_hash, &fidx->uph_link);
+		hash_table_insert(&ui_hash, &fidx->uih_link);
 	}
 	fibril_mutex_lock(&fidx->lock);
@@ -457,12 +448,6 @@
 void fat_idx_hashin(fat_idx_t *idx)
 {
-	unsigned long pkey[] = {
-		[UPH_SID_KEY] = idx->service_id,
-		[UPH_PFC_KEY] = idx->pfc,
-		[UPH_PDI_KEY] = idx->pdi,
-	};
-
-	fibril_mutex_lock(&used_lock);
-	hash_table_insert(&up_hash, pkey, &idx->uph_link);
+	fibril_mutex_lock(&used_lock);
+	hash_table_insert(&up_hash, &idx->uph_link);
 	fibril_mutex_unlock(&used_lock);
 }
@@ -470,12 +455,6 @@
 void fat_idx_hashout(fat_idx_t *idx)
 {
-	unsigned long pkey[] = {
-		[UPH_SID_KEY] = idx->service_id,
-		[UPH_PFC_KEY] = idx->pfc,
-		[UPH_PDI_KEY] = idx->pdi,
-	};
-
-	fibril_mutex_lock(&used_lock);
-	hash_table_remove(&up_hash, pkey, 3);
+	fibril_mutex_lock(&used_lock);
+	hash_table_remove_item(&up_hash, &idx->uph_link);
 	fibril_mutex_unlock(&used_lock);
 }
@@ -532,7 +511,7 @@
 int fat_idx_init(void)
 {
-	if (!hash_table_create(&up_hash, UPH_BUCKETS, 3, &uph_ops)) 
+	if (!hash_table_create(&up_hash, 0, 3, &uph_ops)) 
 		return ENOMEM;
-	if (!hash_table_create(&ui_hash, UIH_BUCKETS, 2, &uih_ops)) {
+	if (!hash_table_create(&ui_hash, 0, 2, &uih_ops)) {
 		hash_table_destroy(&up_hash);
 		return ENOMEM;
Index: uspace/srv/fs/locfs/locfs_ops.c
===================================================================
--- uspace/srv/fs/locfs/locfs_ops.c	(revision 1c1da4bb5da22780fc373a9c9faa4e7fdc641791)
+++ uspace/srv/fs/locfs/locfs_ops.c	(revision 0ca7286a618557bd1d13cded4ccbe25d62752237)
@@ -73,14 +73,25 @@
 #define SERVICES_KEYS        1
 #define SERVICES_KEY_HANDLE  0
-#define SERVICES_BUCKETS     256
 
 /* Implementation of hash table interface for the nodes hash table. */
-static hash_index_t services_hash(unsigned long key[])
-{
-	return key[SERVICES_KEY_HANDLE] % SERVICES_BUCKETS;
-}
-
-static int services_compare(unsigned long key[], hash_count_t keys, link_t *item)
-{
+
+static size_t services_key_hash(unsigned long key[])
+{
+	return key[SERVICES_KEY_HANDLE];
+}
+
+static size_t services_hash(const link_t *item)
+{
+	service_t *dev = hash_table_get_instance(item, service_t, link);
+	unsigned long key[] = {
+		[SERVICES_KEY_HANDLE] = dev->service_id
+	};
+	
+	return services_key_hash(key);
+}
+
+static bool services_match(unsigned long key[], size_t keys, const link_t *item)
+{
+	assert(keys == 1);
 	service_t *dev = hash_table_get_instance(item, service_t, link);
 	return (dev->service_id == (service_id_t) key[SERVICES_KEY_HANDLE]);
@@ -92,7 +103,9 @@
 }
 
-static hash_table_operations_t services_ops = {
+static hash_table_ops_t services_ops = {
 	.hash = services_hash,
-	.compare = services_compare,
+	.key_hash = services_key_hash,
+	.match = services_match,
+	.equal = 0, 
 	.remove_callback = services_remove_callback
 };
@@ -256,5 +269,5 @@
 			 * below.
 			 */
-			hash_table_insert(&services, key, &dev->link);
+			hash_table_insert(&services, &dev->link);
 			
 			/*
@@ -450,6 +463,5 @@
 bool locfs_init(void)
 {
-	if (!hash_table_create(&services, SERVICES_BUCKETS,
-	    SERVICES_KEYS, &services_ops))
+	if (!hash_table_create(&services, 0,  SERVICES_KEYS, &services_ops))
 		return false;
 	
Index: uspace/srv/fs/mfs/mfs_ops.c
===================================================================
--- uspace/srv/fs/mfs/mfs_ops.c	(revision 1c1da4bb5da22780fc373a9c9faa4e7fdc641791)
+++ uspace/srv/fs/mfs/mfs_ops.c	(revision 0ca7286a618557bd1d13cded4ccbe25d62752237)
@@ -40,5 +40,4 @@
 #define OPEN_NODES_SERVICE_KEY 0
 #define OPEN_NODES_INODE_KEY 1
-#define OPEN_NODES_BUCKETS 256
 
 static bool check_magic_number(uint16_t magic, bool *native,
@@ -61,8 +60,8 @@
 static int mfs_unlink(fs_node_t *, fs_node_t *, const char *name);
 static int mfs_destroy_node(fs_node_t *fn);
-static hash_index_t open_nodes_hash(unsigned long key[]);
-static int open_nodes_compare(unsigned long key[], hash_count_t keys,
-    link_t *item);
-static void open_nodes_remove_cb(link_t *link);
+static size_t open_nodes_hash(const link_t *item);
+static size_t open_nodes_key_hash(unsigned long key[]);
+static bool open_nodes_match(unsigned long key[], size_t keys,
+    const link_t *item);
 static int mfs_node_get(fs_node_t **rfn, service_id_t service_id,
     fs_index_t index);
@@ -95,38 +94,47 @@
 
 /* Hash table interface for open nodes hash table */
-static hash_index_t
-open_nodes_hash(unsigned long key[])
-{
-	/* TODO: This is very simple and probably can be improved */
-	return key[OPEN_NODES_INODE_KEY] % OPEN_NODES_BUCKETS;
-}
-
-static int
-open_nodes_compare(unsigned long key[], hash_count_t keys,
-    link_t *item)
-{
+
+static size_t
+open_nodes_key_hash(unsigned long key[])
+{
+	/* As recommended by Effective Java, 2nd Edition. */
+	size_t hash = 17;
+	hash = 37 * hash + key[OPEN_NODES_SERVICE_KEY];
+	hash = 37 * hash + key[OPEN_NODES_INODE_KEY];
+	return hash;
+}
+
+static size_t
+open_nodes_hash(const link_t *item)
+{
+	struct mfs_node *m = hash_table_get_instance(item, struct mfs_node, link);
+	
+	unsigned long key[] = {
+		[OPEN_NODES_SERVICE_KEY] = m->instance->service_id,
+		[OPEN_NODES_INODE_KEY] = m->ino_i->index,
+	};
+	
+	return open_nodes_key_hash(key);
+}
+
+static bool
+open_nodes_match(unsigned long key[], size_t keys, const link_t *item)
+{
+	assert(keys == 2);
 	struct mfs_node *mnode = hash_table_get_instance(item, struct mfs_node, link);
-	assert(keys > 0);
-	if (mnode->instance->service_id !=
-	    ((service_id_t) key[OPEN_NODES_SERVICE_KEY])) {
-		return false;
-	}
-	if (keys == 1) {
-		return true;
-	}
-	assert(keys == 2);
-	return (mnode->ino_i->index == key[OPEN_NODES_INODE_KEY]);
-}
-
-static void
-open_nodes_remove_cb(link_t *link)
-{
-	/* We don't use remove callback for this hash table */
-}
-
-static hash_table_operations_t open_nodes_ops = {
+	
+	service_id_t service_id = ((service_id_t) key[OPEN_NODES_SERVICE_KEY]);
+	
+	return mnode->instance->service_id == service_id
+		&& mnode->ino_i->index == key[OPEN_NODES_INODE_KEY];
+}
+
+
+static hash_table_ops_t open_nodes_ops = {
 	.hash = open_nodes_hash,
-	.compare = open_nodes_compare,
-	.remove_callback = open_nodes_remove_cb,
+	.key_hash = open_nodes_key_hash,
+	.match = open_nodes_match,
+	.equal = 0,
+	.remove_callback = 0,
 };
 
@@ -134,6 +142,5 @@
 mfs_global_init(void)
 {
-	if (!hash_table_create(&open_nodes, OPEN_NODES_BUCKETS,
-	    OPEN_NODES_KEYS, &open_nodes_ops)) {
+	if (!hash_table_create(&open_nodes, 0, OPEN_NODES_KEYS, &open_nodes_ops)) {
 		return ENOMEM;
 	}
@@ -408,11 +415,6 @@
 	link_initialize(&mnode->link);
 
-	unsigned long key[] = {
-		[OPEN_NODES_SERVICE_KEY] = inst->service_id,
-		[OPEN_NODES_INODE_KEY] = inum,
-	};
-
 	fibril_mutex_lock(&open_nodes_lock);
-	hash_table_insert(&open_nodes, key, &mnode->link);
+	hash_table_insert(&open_nodes, &mnode->link);
 	fibril_mutex_unlock(&open_nodes_lock);
 	inst->open_nodes_cnt++;
@@ -621,5 +623,5 @@
 	*rfn = node;
 
-	hash_table_insert(&open_nodes, key, &mnode->link);
+	hash_table_insert(&open_nodes, &mnode->link);
 	inst->open_nodes_cnt++;
 
Index: uspace/srv/fs/tmpfs/tmpfs_ops.c
===================================================================
--- uspace/srv/fs/tmpfs/tmpfs_ops.c	(revision 1c1da4bb5da22780fc373a9c9faa4e7fdc641791)
+++ uspace/srv/fs/tmpfs/tmpfs_ops.c	(revision 0ca7286a618557bd1d13cded4ccbe25d62752237)
@@ -56,6 +56,4 @@
 #define max(a, b)		((a) > (b) ? (a) : (b))
 
-#define NODES_BUCKETS	256
-
 /** All root nodes have index 0. */
 #define TMPFS_SOME_ROOT		0
@@ -146,10 +144,26 @@
 
 /* Implementation of hash table interface for the nodes hash table. */
-static hash_index_t nodes_hash(unsigned long key[])
-{
-	return key[NODES_KEY_INDEX] % NODES_BUCKETS;
-}
-
-static int nodes_compare(unsigned long key[], hash_count_t keys, link_t *item)
+static size_t nodes_key_hash(unsigned long key[])
+{
+	/* Based on Effective Java, 2nd Edition. */
+	size_t hash = 17;
+	hash = 37 * hash + key[NODES_KEY_DEV];
+	hash = 37 * hash + key[NODES_KEY_INDEX];
+	return hash;
+}
+
+static size_t nodes_hash(const link_t *item)
+{
+	tmpfs_node_t *nodep = hash_table_get_instance(item, tmpfs_node_t, nh_link);
+	
+	unsigned long key[] = {
+		[NODES_KEY_DEV] = nodep->service_id,
+		[NODES_KEY_INDEX] = nodep->index
+	};
+	
+	return nodes_key_hash(key);
+}
+
+static bool nodes_match(unsigned long key[], size_t keys, const link_t *item)
 {
 	tmpfs_node_t *nodep = hash_table_get_instance(item, tmpfs_node_t,
@@ -192,7 +206,9 @@
 
 /** TMPFS nodes hash table operations. */
-hash_table_operations_t nodes_ops = {
+hash_table_ops_t nodes_ops = {
 	.hash = nodes_hash,
-	.compare = nodes_compare,
+	.key_hash = nodes_key_hash,
+	.match = nodes_match,
+	.equal = 0,
 	.remove_callback = nodes_remove_callback
 };
@@ -220,5 +236,5 @@
 bool tmpfs_init(void)
 {
-	if (!hash_table_create(&nodes, NODES_BUCKETS, 2, &nodes_ops))
+	if (!hash_table_create(&nodes, 0, 2, &nodes_ops))
 		return false;
 	
@@ -331,9 +347,5 @@
 
 	/* Insert the new node into the nodes hash table. */
-	unsigned long key[] = {
-		[NODES_KEY_DEV] = nodep->service_id,
-		[NODES_KEY_INDEX] = nodep->index
-	};
-	hash_table_insert(&nodes, key, &nodep->nh_link);
+	hash_table_insert(&nodes, &nodep->nh_link);
 	*rfn = FS_NODE(nodep);
 	return EOK;
Index: uspace/srv/hid/input/generic/gsp.c
===================================================================
--- uspace/srv/hid/input/generic/gsp.c	(revision 1c1da4bb5da22780fc373a9c9faa4e7fdc641791)
+++ uspace/srv/hid/input/generic/gsp.c	(revision 0ca7286a618557bd1d13cded4ccbe25d62752237)
@@ -54,19 +54,18 @@
 #include <stdio.h>
 
-#define TRANS_TABLE_CHAINS 256
-
 /*
  * Hash table operations for the transition function.
  */
 
-static hash_index_t trans_op_hash(unsigned long key[]);
-static int trans_op_compare(unsigned long key[], hash_count_t keys,
-    link_t *item);
-static void trans_op_remove_callback(link_t *item);
-
-static hash_table_operations_t trans_ops = {
+static size_t trans_op_hash(const link_t *item);
+static size_t trans_op_key_hash(unsigned long key[]);
+static bool trans_op_match(unsigned long key[], size_t keys, const link_t *item);
+
+static hash_table_ops_t trans_ops = {
 	.hash = trans_op_hash,
-	.compare = trans_op_compare,
-	.remove_callback = trans_op_remove_callback
+	.key_hash = trans_op_key_hash,
+	.match = trans_op_match,
+	.equal = 0,
+	.remove_callback = 0
 };
 
@@ -75,9 +74,9 @@
 static gsp_trans_t *trans_new(void);
 
-/** Initialise scancode parser. */
+/** Initialize scancode parser. */
 void gsp_init(gsp_t *p)
 {
 	p->states = 1;
-	hash_table_create(&p->trans, TRANS_TABLE_CHAINS, 2, &trans_ops);
+	hash_table_create(&p->trans, 0, 2, &trans_ops);
 }
 
@@ -242,10 +241,5 @@
 static void trans_insert(gsp_t *p, gsp_trans_t *t)
 {
-	unsigned long key[2];
-
-	key[0] = t->old_state;
-	key[1] = t->input;
-
-	hash_table_insert(&p->trans, key, &t->link);
+	hash_table_insert(&p->trans, &t->link);
 }
 
@@ -268,21 +262,25 @@
  */
 
-static hash_index_t trans_op_hash(unsigned long key[])
-{
-	return (key[0] * 17 + key[1]) % TRANS_TABLE_CHAINS;
-}
-
-static int trans_op_compare(unsigned long key[], hash_count_t keys,
-    link_t *item)
-{
-	gsp_trans_t *t;
-
-	t = hash_table_get_instance(item, gsp_trans_t, link);
+static size_t trans_op_key_hash(unsigned long key[])
+{
+	return (key[0] * 17 + key[1]);
+}
+
+static size_t trans_op_hash(const link_t *item)
+{
+	gsp_trans_t *t = hash_table_get_instance(item, gsp_trans_t, link);
+	unsigned long key[] = {
+		t->old_state,
+		t->input
+	};
+	
+	return trans_op_key_hash(key);
+}
+
+static bool trans_op_match(unsigned long key[], size_t keys, const link_t *item)
+{
+	gsp_trans_t *t = hash_table_get_instance(item, gsp_trans_t, link);
 	return ((key[0] == (unsigned long) t->old_state)
 	    && (key[1] == (unsigned long) t->input));
-}
-
-static void trans_op_remove_callback(link_t *item)
-{
 }
 
Index: uspace/srv/ns/service.c
===================================================================
--- uspace/srv/ns/service.c	(revision 1c1da4bb5da22780fc373a9c9faa4e7fdc641791)
+++ uspace/srv/ns/service.c	(revision 0ca7286a618557bd1d13cded4ccbe25d62752237)
@@ -40,5 +40,4 @@
 #include "ns.h"
 
-#define SERVICE_HASH_TABLE_CHAINS  20
 
 /** Service hash table item. */
@@ -58,8 +57,15 @@
  *
  */
-static hash_index_t service_hash(unsigned long key[])
+static size_t service_key_hash(unsigned long key[])
 {
 	assert(key);
-	return (key[0] % SERVICE_HASH_TABLE_CHAINS);
+	return key[0];
+}
+
+static size_t service_hash(const link_t *item)
+{
+	hashed_service_t *hs = hash_table_get_instance(item, hashed_service_t, link);
+	unsigned long key = hs->service;
+	return service_key_hash(&key);
 }
 
@@ -79,5 +85,5 @@
  *
  */
-static int service_compare(unsigned long key[], hash_count_t keys, link_t *item)
+static bool service_match(unsigned long key[], size_t keys, const link_t *item)
 {
 	assert(key);
@@ -105,7 +111,9 @@
 
 /** Operations for service hash table. */
-static hash_table_operations_t service_hash_table_ops = {
+static hash_table_ops_t service_hash_table_ops = {
 	.hash = service_hash,
-	.compare = service_compare,
+	.key_hash = service_key_hash,
+	.match = service_match,
+	.equal = 0,
 	.remove_callback = service_remove
 };
@@ -127,6 +135,5 @@
 int service_init(void)
 {
-	if (!hash_table_create(&service_hash_table, SERVICE_HASH_TABLE_CHAINS,
-	    3, &service_hash_table_ops)) {
+	if (!hash_table_create(&service_hash_table, 0, 3, &service_hash_table_ops)) {
 		printf(NAME ": No memory available for services\n");
 		return ENOMEM;
@@ -193,5 +200,5 @@
 	hs->phone = phone;
 	hs->in_phone_hash = call->in_phone_hash;
-	hash_table_insert(&service_hash_table, keys, &hs->link);
+	hash_table_insert(&service_hash_table, &hs->link);
 	
 	return EOK;
Index: uspace/srv/ns/task.c
===================================================================
--- uspace/srv/ns/task.c	(revision 1c1da4bb5da22780fc373a9c9faa4e7fdc641791)
+++ uspace/srv/ns/task.c	(revision 0ca7286a618557bd1d13cded4ccbe25d62752237)
@@ -43,6 +43,4 @@
 #include "ns.h"
 
-#define TASK_HASH_TABLE_CHAINS  256
-#define P2I_HASH_TABLE_CHAINS   256
 
 /* TODO:
@@ -71,8 +69,22 @@
  *
  */
-static hash_index_t task_hash(unsigned long key[])
-{
-	assert(key);
-	return (LOWER32(key[0]) % TASK_HASH_TABLE_CHAINS);
+static size_t task_key_hash(unsigned long key[])
+{
+	size_t hash = 17;
+	hash = 37 * hash + key[1];
+	hash = 37 * hash + key[0];
+	return hash;
+}
+
+static size_t task_hash(const link_t *item)
+{
+	hashed_task_t *ht = hash_table_get_instance(item, hashed_task_t, link);
+
+	unsigned long key[] = {
+		LOWER32(ht->id),
+		UPPER32(ht->id)
+	};
+	
+	return task_key_hash(key);
 }
 
@@ -86,17 +98,14 @@
  *
  */
-static int task_compare(unsigned long key[], hash_count_t keys, link_t *item)
+static bool task_match(unsigned long key[], size_t keys, const link_t *item)
 {
 	assert(key);
-	assert(keys <= 2);
+	assert(keys == 2);
 	assert(item);
 	
 	hashed_task_t *ht = hash_table_get_instance(item, hashed_task_t, link);
 	
-	if (keys == 2)
-		return ((LOWER32(key[1]) == UPPER32(ht->id))
-		    && (LOWER32(key[0]) == LOWER32(ht->id)));
-	else
-		return (LOWER32(key[0]) == LOWER32(ht->id));
+	return (key[0] == LOWER32(ht->id))
+		&& (key[1] == UPPER32(ht->id));
 }
 
@@ -113,7 +122,9 @@
 
 /** Operations for task hash table. */
-static hash_table_operations_t task_hash_table_ops = {
+static hash_table_ops_t task_hash_table_ops = {
 	.hash = task_hash,
-	.compare = task_compare,
+	.key_hash = task_key_hash,
+	.match = task_match,
+	.equal = 0,
 	.remove_callback = task_remove
 };
@@ -135,8 +146,15 @@
  *
  */
-static hash_index_t p2i_hash(unsigned long key[])
+static size_t p2i_key_hash(unsigned long key[])
 {
 	assert(key);
-	return (key[0] % TASK_HASH_TABLE_CHAINS);
+	return key[0];
+}
+
+static size_t p2i_hash(const link_t *item)
+{
+	p2i_entry_t *entry = hash_table_get_instance(item, p2i_entry_t, link);
+	unsigned long key = entry->in_phone_hash;
+	return p2i_key_hash(&key);
 }
 
@@ -150,5 +168,5 @@
  *
  */
-static int p2i_compare(unsigned long key[], hash_count_t keys, link_t *item)
+static bool p2i_match(unsigned long key[], size_t keys, const link_t *item)
 {
 	assert(key);
@@ -173,7 +191,9 @@
 
 /** Operations for task hash table. */
-static hash_table_operations_t p2i_ops = {
+static hash_table_ops_t p2i_ops = {
 	.hash = p2i_hash,
-	.compare = p2i_compare,
+	.key_hash = p2i_key_hash,
+	.match = p2i_match,
+	.equal = 0,
 	.remove_callback = p2i_remove
 };
@@ -193,12 +213,10 @@
 int task_init(void)
 {
-	if (!hash_table_create(&task_hash_table, TASK_HASH_TABLE_CHAINS,
-	    2, &task_hash_table_ops)) {
+	if (!hash_table_create(&task_hash_table, 0, 2, &task_hash_table_ops)) {
 		printf(NAME ": No memory available for tasks\n");
 		return ENOMEM;
 	}
 	
-	if (!hash_table_create(&phone_to_id, P2I_HASH_TABLE_CHAINS,
-	    1, &p2i_ops)) {
+	if (!hash_table_create(&phone_to_id, 0, 1, &p2i_ops)) {
 		printf(NAME ": No memory available for tasks\n");
 		return ENOMEM;
@@ -293,8 +311,8 @@
 int ns_task_id_intro(ipc_call_t *call)
 {
-	unsigned long keys[2];
 	
 	task_id_t id = MERGE_LOUP32(IPC_GET_ARG1(*call), IPC_GET_ARG2(*call));
-	keys[0] = call->in_phone_hash;
+
+	unsigned long keys[] = { call->in_phone_hash };
 	
 	link_t *link = hash_table_find(&phone_to_id, keys);
@@ -317,12 +335,9 @@
 	entry->in_phone_hash = call->in_phone_hash;
 	entry->id = id;
-	hash_table_insert(&phone_to_id, keys, &entry->link);
+	hash_table_insert(&phone_to_id, &entry->link);
 	
 	/*
 	 * Insert into the main table.
 	 */
-	
-	keys[0] = LOWER32(id);
-	keys[1] = UPPER32(id);
 	
 	link_initialize(&ht->link);
@@ -331,5 +346,5 @@
 	ht->have_rval = false;
 	ht->retval = -1;
-	hash_table_insert(&task_hash_table, keys, &ht->link);
+	hash_table_insert(&task_hash_table, &ht->link);
 	
 	return EOK;
Index: uspace/srv/vfs/vfs_node.c
===================================================================
--- uspace/srv/vfs/vfs_node.c	(revision 1c1da4bb5da22780fc373a9c9faa4e7fdc641791)
+++ uspace/srv/vfs/vfs_node.c	(revision 0ca7286a618557bd1d13cded4ccbe25d62752237)
@@ -58,13 +58,15 @@
 #define KEY_INDEX	2
 
-static hash_index_t nodes_hash(unsigned long []);
-static int nodes_compare(unsigned long [], hash_count_t, link_t *);
-static void nodes_remove_callback(link_t *);
+static size_t nodes_key_hash(unsigned long []);
+static size_t nodes_hash(const link_t *);
+static bool nodes_match(unsigned long [], size_t, const link_t *);
 
 /** VFS node hash table operations. */
-hash_table_operations_t nodes_ops = {
+hash_table_ops_t nodes_ops = {
 	.hash = nodes_hash,
-	.compare = nodes_compare,
-	.remove_callback = nodes_remove_callback
+	.key_hash = nodes_key_hash,
+	.match = nodes_match,
+	.equal = 0,
+	.remove_callback = 0,
 };
 
@@ -75,5 +77,5 @@
 bool vfs_nodes_init(void)
 {
-	return hash_table_create(&nodes, NODES_BUCKETS, 3, &nodes_ops);
+	return hash_table_create(&nodes, 0, 3, &nodes_ops);
 }
 
@@ -207,5 +209,5 @@
 		link_initialize(&node->nh_link);
 		fibril_rwlock_initialize(&node->contents_rwlock);
-		hash_table_insert(&nodes, key, &node->nh_link);
+		hash_table_insert(&nodes, &node->nh_link);
 	} else {
 		node = hash_table_get_instance(tmp, vfs_node_t, nh_link);
@@ -240,13 +242,29 @@
 }
 
-hash_index_t nodes_hash(unsigned long key[])
-{
-	hash_index_t a = key[KEY_FS_HANDLE] << (NODES_BUCKETS_LOG / 4);
-	hash_index_t b = (a | key[KEY_DEV_HANDLE]) << (NODES_BUCKETS_LOG / 2);
-	
-	return (b | key[KEY_INDEX]) & (NODES_BUCKETS - 1);
-}
-
-int nodes_compare(unsigned long key[], hash_count_t keys, link_t *item)
+size_t nodes_key_hash(unsigned long key[])
+{
+	/* Combine into a hash like they do in Effective Java, 2nd edition. */
+	size_t hash = 17;
+	hash = 37 * hash + key[KEY_FS_HANDLE];
+	hash = 37 * hash + key[KEY_DEV_HANDLE];
+	hash = 37 * hash + key[KEY_INDEX];
+	return hash;
+}
+
+size_t nodes_hash(const link_t *item)
+{
+	vfs_node_t *node = hash_table_get_instance(item, vfs_node_t, nh_link);
+	
+	unsigned long key[] = {
+		[KEY_FS_HANDLE] = node->fs_handle,
+		[KEY_DEV_HANDLE] = node->service_id,
+		[KEY_INDEX] = node->index
+	};
+	
+	return nodes_key_hash(key);
+}
+
+
+bool nodes_match(unsigned long key[], size_t keys, const link_t *item)
 {
 	vfs_node_t *node = hash_table_get_instance(item, vfs_node_t, nh_link);
@@ -256,7 +274,4 @@
 }
 
-void nodes_remove_callback(link_t *item)
-{
-}
 
 struct refcnt_data {
@@ -267,5 +282,5 @@
 };
 
-static void refcnt_visitor(link_t *item, void *arg)
+static bool refcnt_visitor(link_t *item, void *arg)
 {
 	vfs_node_t *node = hash_table_get_instance(item, vfs_node_t, nh_link);
@@ -275,4 +290,6 @@
 	    (node->service_id == rd->service_id))
 		rd->refcnt += node->refcnt;
+	
+	return true;
 }
 
