Index: uspace/srv/devman/devman.c
===================================================================
--- uspace/srv/devman/devman.c	(revision a3fcfbab8ada7658810ed4966e92d5dc1f3cfec7)
+++ uspace/srv/devman/devman.c	(revision 2732c94b5bd8edf3ef46b0da6138cc7619bd3be5)
@@ -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 a3fcfbab8ada7658810ed4966e92d5dc1f3cfec7)
+++ uspace/srv/devman/devman.h	(revision 2732c94b5bd8edf3ef46b0da6138cc7619bd3be5)
@@ -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 a3fcfbab8ada7658810ed4966e92d5dc1f3cfec7)
+++ uspace/srv/fs/cdfs/cdfs_ops.c	(revision 2732c94b5bd8edf3ef46b0da6138cc7619bd3be5)
@@ -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 a3fcfbab8ada7658810ed4966e92d5dc1f3cfec7)
+++ uspace/srv/fs/exfat/exfat_idx.c	(revision 2732c94b5bd8edf3ef46b0da6138cc7619bd3be5)
@@ -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 a3fcfbab8ada7658810ed4966e92d5dc1f3cfec7)
+++ uspace/srv/fs/ext2fs/ext2fs_ops.c	(revision 2732c94b5bd8edf3ef46b0da6138cc7619bd3be5)
@@ -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 a3fcfbab8ada7658810ed4966e92d5dc1f3cfec7)
+++ uspace/srv/fs/fat/fat_idx.c	(revision 2732c94b5bd8edf3ef46b0da6138cc7619bd3be5)
@@ -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 a3fcfbab8ada7658810ed4966e92d5dc1f3cfec7)
+++ uspace/srv/fs/locfs/locfs_ops.c	(revision 2732c94b5bd8edf3ef46b0da6138cc7619bd3be5)
@@ -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 a3fcfbab8ada7658810ed4966e92d5dc1f3cfec7)
+++ uspace/srv/fs/mfs/mfs_ops.c	(revision 2732c94b5bd8edf3ef46b0da6138cc7619bd3be5)
@@ -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 a3fcfbab8ada7658810ed4966e92d5dc1f3cfec7)
+++ uspace/srv/fs/tmpfs/tmpfs_ops.c	(revision 2732c94b5bd8edf3ef46b0da6138cc7619bd3be5)
@@ -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 a3fcfbab8ada7658810ed4966e92d5dc1f3cfec7)
+++ uspace/srv/hid/input/generic/gsp.c	(revision 2732c94b5bd8edf3ef46b0da6138cc7619bd3be5)
@@ -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 a3fcfbab8ada7658810ed4966e92d5dc1f3cfec7)
+++ uspace/srv/ns/service.c	(revision 2732c94b5bd8edf3ef46b0da6138cc7619bd3be5)
@@ -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 a3fcfbab8ada7658810ed4966e92d5dc1f3cfec7)
+++ uspace/srv/ns/task.c	(revision 2732c94b5bd8edf3ef46b0da6138cc7619bd3be5)
@@ -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 a3fcfbab8ada7658810ed4966e92d5dc1f3cfec7)
+++ uspace/srv/vfs/vfs_node.c	(revision 2732c94b5bd8edf3ef46b0da6138cc7619bd3be5)
@@ -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;
 }