Hashtable

原文链接： Javarevisited 翻译： ImportNew.com - 唐小娟译文链接： http://www.importnew.com/7010...HashMap和Hashtable的比较是Java面试中的常见问题，用来考验程序员是否能够正确使用集合类以及是否可以随机应变使用多种思路解决问题。HashMap的工作原理、ArrayList与Vector的比较以及这个问题是有关Java 集合框架的最经典的问题。Hashtable是个过时的集合类，存在于Java API中很久了。在Java 4中被重写了，实现了Map接口，所以自此以后也成了Java集合框架中的一部分。Hashtable和HashMap在Java面试中相当容易被问到，甚至成为了集合框架面试题中最常被考的问题，所以在参加任何Java面试之前，都不要忘了准备这一题。这篇文章中，我们不仅将会看到HashMap和Hashtable的区别，还将看到它们之间的相似之处。HashMap和Hashtable的区别HashMap和Hashtable都实现了Map接口，但决定用哪一个之前先要弄清楚它们之间的分别。主要的区别有：线程安全性，同步(synchronization)，以及速度。HashMap几乎可以等价于Hashtable，除了HashMap是非synchronized的，并可以接受null(HashMap可以接受为null的键值(key)和值(value)，而Hashtable则不行)。HashMap是非synchronized，而Hashtable是synchronized，这意味着Hashtable是线程安全的，多个线程可以共享一个Hashtable；而如果没有正确的同步的话，多个线程是不能共享HashMap的。Java 5提供了ConcurrentHashMap，它是HashTable的替代，比HashTable的扩展性更好。另一个区别是HashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的。所以当有其它线程改变了HashMap的结构（增加或者移除元素），将会抛出ConcurrentModificationException，但迭代器本身的remove()方法移除元素则不会抛出ConcurrentModificationException异常。但这并不是一个一定发生的行为，要看JVM。这条同样也是Enumeration和Iterator的区别。由于Hashtable是线程安全的也是synchronized，所以在单线程环境下它比HashMap要慢。如果你不需要同步，只需要单一线程，那么使用HashMap性能要好过Hashtable。HashMap不能保证随着时间的推移Map中的元素次序是不变的。要注意的一些重要术语：sychronized意味着在一次仅有一个线程能够更改Hashtable。就是说任何线程要更新Hashtable时要首先获得同步锁，其它线程要等到同步锁被释放之后才能再次获得同步锁更新Hashtable。Fail-safe和iterator迭代器相关。如果某个集合对象创建了Iterator或者ListIterator，然后其它的线程试图“结构上”更改集合对象，将会抛出ConcurrentModificationException异常。但其它线程可以通过set()方法更改集合对象是允许的，因为这并没有从“结构上”更改集合。但是假如已经从结构上进行了更改，再调用set()方法，将会抛出IllegalArgumentException异常。结构上的更改指的是删除或者插入一个元素，这样会影响到map的结构。我们能否让HashMap同步？HashMap可以通过下面的语句进行同步：Map m = Collections.synchronizeMap(hashMap);结论Hashtable和HashMap有几个主要的不同：线程安全以及速度。仅在你需要完全的线程安全的时候使用Hashtable，Hashtable是java 4时代的过时产物，ConcurrentHashMap是它的替代品。而如果你使用Java 5或以上的话，请使用ConcurrentHashMap吧。

上一章我们讲了如何根据需要动态设置hash表的大小，在第四章中，我们使用了双重哈希来解决hash表的碰撞，其实解决方法有很多，这一章我们来介绍下其他方法。本章将介绍两种解决hash表碰撞的方法：拉链法开放地址法拉链法使用拉链法，每一个bucket都会包含一个链接表，当发生碰撞时，就会将该记录插入在该位置的链接表后面，步骤如下：插入时：通过hash函数获取到要插入的位置，如果该位置是空的，就直接插入，如果该位置不是空的，就插入在链接表的后面搜索时：通过hash函数获取到key对应的位置，遍历链接表，判断key是不是搜索的key，如果是，则返回value，否则返回NULL删除时：通过hash函数获取到key对应的位置，遍历链接表，找到需要删除的key，如果找到，则将该key对应的记录从链接表中删除，如果链接表中只有一条记录，则将该位置置为NULL拉链法的优点是实现起来简单，但是空间利用率低。每个记录必须存储指向链接表中下一个记录的指针，如果没有记录，则指向NULL，这种方法会浪费一些空间来存储额外的指针。开放地址法开放地址法能解决拉链法空间利用率低的问题，发生碰撞时，碰撞的记录将放置在hash表中的其他bucket中，存放的位置是根据预先确定的规则选择的，以便在搜索记录时可以重复该规则，有如下几种规则：线性探查当发生碰撞时，就会递增索引，将记录插入在下一个可用的索引中，方法如下：插入时：通过hash函数找到插入的位置的索引，如果这个位置是空的，直接插入，如果不为空，就递增索引，直到找到索引指向的位置是空的为止，然后执行插入搜索时：通过hash函数找到搜索的记录的索引，每次递增索引，并比较索引指向的值是否是要搜索的值，如果索引指向的是空，则返回NULL删除时：通过hash函数找到删除的记录的索引，每次递增索引，直到找到要删除的那个key后执行删除线性探测提供了良好的缓存性能，但是存在碰撞后遍历次数多的问题。将发生碰撞的key放入下一个可用的bucket中可能导致后面插入记录也要往后插，就需要多次迭代。二次探查二次探查法和先行探查类似，不同的是，发生碰撞后，我们会将记录插入在如下的序列中：i, i + 1, i + 4, i + 9, i + 16, …，i代表通过hash函数获取到的索引，具体步骤如下：插入时：通过hash函数找到插入的索引，通过遍历上面的序列直到找到一个空的或已被删除的索引位置，执行插入搜索时：通过hash函数找到key的索引，遍历上面的序列，将序列上的key与搜索的key对比，如果相等，则返回value，否则返回NULL删除时：因为我们无法判断要删除的项是不是碰撞链上的，所以我们不能直接删除该条记录，只能把它标记为已删除二次探查法减少发生碰撞后遍历的次数，并且仍然提供了不错的缓存性能。双重hash双重hash旨在解决碰撞后遍历次数多的问题。使用两次hash函数为插入的记录选择新的索引，这个索引会均匀的分布在整个表中，该方法虽然解决了上述问题，但也失去了缓存特性，双重hash是实际项目中常见的冲突管理方法，也是我们在本教程中实现的方法。上一章：设置hash表大小

上一章中，我们实现了Hash表中的插入、搜索和删除接口，我们在初始化hash表时固定了大小为53，为了方便扩展，本章将介绍如何修改hash表的大小。设置Hash表大小现在，我们的hash表是固定大小(53)的，当插入越来越多数据时，我们的hash表就会被插满，这个问题有两个原因：哈希表的性能随着高冲突率而降低我们的’hash表’只能存储固定数量的记录，如果我们存储更多，将无法插入数据为了减少hash表被插满的情况发生，当插入很多数据时，我们可以增大hash表的大小，hash表中的count属性代表已经插入的数据条数，在每次插入和删除时，我们计算表的“负载”，或插入的数量和总的大小的比率，如果它高于或低于某些值，我们会减小或扩大hash表的大小。我们定义如下规则：如果负载>0.7，就扩大如果负载<0.1，就缩小要调整大小，我们创建一个大约是当前大小的一半或两倍的新哈希表，并将所有未删除的项插入其中。我们的新hash表大小应该是大约是当前大小的两倍或一半的素数，找到新的hash表大小并非易事。为了确定hash表的大小，我们现设置一个最基本的大小，然后将实际大小定义为大于基本大小的第一个素数。扩大时，我们先将基本大小加倍，找到第一个更大的素数，然后作为hash表的大小，缩小时，我们将大小减半并找到下一个更大的素数。我们先从基本大小50开始，我们使用最简单粗暴的方法通过检查每个连续数是否为素数来查找下一个素数。这个简单粗暴的方法看起来不是很理想，但是我们实际需要检查的值很少，并且花费的时间超过了重新散列表中每个项目所花费的时间。首先，我们先定义一个函数用来找到下一个素数，prime.h和prime.c的内容如下：// prime.hint is_prime(const int x);int next_prime(int x);// prime.c#include <math.h>#include “prime.h”/* * Return whether x is prime or not * * Returns: * 1 - prime * 0 - not prime * -1 - undefined (i.e. x < 2) /int is_prime(const int x) { if (x < 2) { return -1; } if (x < 4) { return 1; } if ((x % 2) == 0) { return 0; } for (int i = 3; i <= floor(sqrt((double) x)); i += 2) { if ((x % i) == 0) { return 0; } } return 1;}/ * Return the next prime after x, or x if x is prime /int next_prime(int x) { while (is_prime(x) != 1) { x++; } return x;}下一步，我们需要修改ht_new函数，使之可以在创建hash表时指定大小，为此我们要创建一个新的函数ht_new_sized，在ht_new中我们调用ht_new_sized并给我们的hash表一个默认大小：// hash_table.cstatic ht_hash_table ht_new_sized(const int base_size) { ht_hash_table* ht = xmalloc(sizeof(ht_hash_table)); ht->base_size = base_size; ht->size = next_prime(ht->base_size); ht->count = 0; ht->items = xcalloc((size_t)ht->size, sizeof(ht_item*)); return ht;}ht_hash_table* ht_new() { return ht_new_sized(HT_INITIAL_BASE_SIZE);}现在一切准备就绪。在我们的设置hash表大小函数中，我们需要检查以确保我们没有将哈希表的大小减小到最小值以下，然后，我们初始化一个所需大小的新hash表，原表中所有非NULL或者未被删除的都会插入到新hash表中，然后我们在删除旧的hash表之前将属性赋值给新的hash表。// hash_table.cstatic void ht_resize(ht_hash_table* ht, const int base_size) { if (base_size < HT_INITIAL_BASE_SIZE) { return; } ht_hash_table* new_ht = ht_new_sized(base_size); for (int i = 0; i < ht->size; i++) { ht_item* item = ht->items[I]; if (item != NULL && item != &HT_DELETED_ITEM) { ht_insert(new_ht, item->key, item->value); } } ht->base_size = new_ht->base_size; ht->count = new_ht->count; // To delete new_ht, we give it ht’s size and items const int tmp_size = ht->size; ht->size = new_ht->size; new_ht->size = tmp_size; ht_item** tmp_items = ht->items; ht->items = new_ht->items; new_ht->items = tmp_items; ht_del_hash_table(new_ht);}为了简化设置大小，我们定义了两个函数：// hash_table.cstatic void ht_resize_up(ht_hash_table* ht) { const int new_size = ht->base_size * 2; ht_resize(ht, new_size);}static void ht_resize_down(ht_hash_table* ht) { const int new_size = ht->base_size / 2; ht_resize(ht, new_size);}要执行调整大小，我们先检查插入和删除时hash表上的负载。 如果它高于或低于0.7和0.1的预定义限制，我们分别调高或调低。为了避免进行浮点运算，我们将计数乘以100，并检查它是高于还是低于70或10：// hash_table.cvoid ht_insert(ht_hash_table* ht, const char* key, const char* value) { const int load = ht->count * 100 / ht->size; if (load > 70) { ht_resize_up(ht); } // …}void ht_delete(ht_hash_table* ht, const char* key) { const int load = ht->count * 100 / ht->size; if (load < 10) { ht_resize_down(ht); } // …}上一章：实现接口下一章：附录：替代碰撞处理 ...

上一章中，我们使用了双重Hash的技术来处理碰撞，并用了C语言实现，贲张我们将实现Hash表中的插入、搜索和删除接口。实现接口我们的hash函数将会实现如下的接口：// hash_table.hvoid ht_insert(ht_hash_table* ht, const char* key, const char* value);char* ht_search(ht_hash_table* ht, const char* key);void ht_delete(ht_hash_table* ht, const char* key);Insert函数在hash表中插入一条记录时，我们需要遍历整个hash表知道找到一个空的位置，然后执行插入并将hash表的大小加1。hash表中的count属性代表hash表的大小，在下一章缩放hash表大小中很有用：void ht_insert(ht_hash_table* ht, const char* key, const char* value) { ht_item* item = ht_new_item(key, value); int index = ht_get_hash(item->key, ht->size, 0); ht_item* cur_item = ht->items[index]; int i = 1; while(cur_item != NULL) { index = ht_get_hash(item->key, ht->size, i); cur_item = ht->items[index]; ++i; } ht->items[index] = item; ht->count++;}Search函数search和insert有点相似，但是在while循环中，我们会检查记录的key是否与我们正在搜索的key匹配。如果匹配，就会返回这条记录的value，没有匹配到就会返回NULL：char* ht_search(ht_hash_table* ht, const char* key) { int index = ht_get_hash(key, ht->size, 0); ht_item* item = ht->items[index]; int i = 1; while (item != NULL) { if (strcmp(item->key, key) == 0) { return item->value; } index = ht_get_hash(key, ht->size, i); item = ht->items[index]; i++; } return NULL;}delete函数从开放的地址hash表中删除比插入或搜索更复杂，因为存在碰撞，我们希望删除的记录可能是碰撞链的一部分。从表中删除它会破坏该链，并且无法在链的尾部找到记录。要解决此问题，我们只需将其标记为已删除，而不是真的删除该记录。我们将记录替换为指向全局哨兵的指针，再将其标记为已删除，该全局哨兵表示包含已删除的记录的bucket：// hash_table.cstatic ht_item HT_DELETED_ITEM = {NULL, NULL};void ht_delete(ht_hash_table* ht, const char* key) { int index = ht_get_hash(key, ht->size, 0); ht_item* item = ht->items[index]; int i = 1; while (item != NULL) { if (item != &HT_DELETED_ITEM) { if (strcmp(item->key, key) == 0) { ht_del_item(item); ht->items[index] = &HT_DELETED_ITEM; } } index = ht_get_hash(key, ht->size, i); item = ht->items[index]; i++; } ht->count–;}删除后，我们需要将hash表的count属性减1。我们也需要修改下ht_insert和ht_search函数，当搜索时，我们需要忽略并跳过已删除的项，在已删除项的位置我们可以插入新的记录：// hash_table.cvoid ht_insert(ht_hash_table* ht, const char* key, const char* value) { // … while (cur_item != NULL && cur_item != &HT_DELETED_ITEM) { // … } // …}char* ht_search(ht_hash_table* ht, const char* key) { // … while (item != NULL) { if (item != &HT_DELETED_ITEM) { if (strcmp(item->key, key) == 0) { return item->value; } } // … } // …}修改一下我们的hash表现在还不支持更新key的值，如果我们插入两条相同key的记录，key将会冲突，第二条记录就会插入到下一个可用的位置，当使用key搜索时，我们会找到第一条记录，第二条记录就永远不会被找到，现在我们修改下ht_insert函数，在插入多条相同key的记录时，会删除之前的记录再插入新的记录：// hash_table.cvoid ht_insert(ht_hash_table* ht, const char* key, const char* value) { // … while (cur_item != NULL) { if (cur_item != &HT_DELETED_ITEM) { if (strcmp(cur_item->key, key) == 0) { ht_del_item(cur_item); ht->items[index] = item; return; } } // … } // …}上一章：处理碰撞下一章：缩放Hash表大小 ...

上一章我们解释了Hash table中最重要的hash函数，并用伪代码和C语言实现了一个我们自己的hash函数，hash函数中碰撞是无法避免的，当发生碰撞时我们改如何有效的处理呢？这章我们就来讲解下。处理碰撞hash函数中将无限大的输入映射到有限的输出中，当不同的输入映射到相同的输出时，就会发生碰撞，每个的hash表都会采用不同的方法来处理碰撞。我们的哈希表将使用一种称为开放地址的双重哈希的技术来处理冲突。双重哈希使用两个散列函数来计算在发生碰撞后存储记录的索引。双重哈希当i发生碰撞后我们使用如下方式来获取索引：index = hash_a(string) + i * hash_b(string) % num_buckets当没有发生碰撞时，i=0，所以索引就是hash_a的值，发生碰撞后，hash_a的结果就需要经过一次hash_b的处理。hash_b可能会返回0，将第二项减少到0，这就导致hash表会将多个记录插入到同一个bucket中，我们可以在hash_b的结果后加1来处理这种情况，确保它永远不会为0：index = (hash_a(string) + i * (hash_b(string) + 1)) % num_buckets算法实现// hash_table.cstatic int ht_get_hash(const char* s, const int num_buckets, const int attempt) { const int hash_a = ht_hash(s, HT_PRIME_1, num_buckets); const int hash_b = ht_hash(s, HT_PRIME_2, num_buckets); return (hash_a + (attempt * (hash_b + 1))) % num_buckets;}上一章：hash函数下一章：完成Hash表API

上一章，我们讲了hash表的数据结构，并简单实现了hash表的初始化与删除操作，这一章我们会讲解Hash函数和实现算法，并手动实现一个Hash函数。Hash函数本教程中我们实现的Hash函数将会实现如下操作：输入一个字符串，然后返回一个0到m(Hash表的大小)的数字为一组平常的输入返回均匀的bucket索引。如果Hash函数不是均匀分布的，就会将多个记录插入到相同的bucket中，这就回提高冲突的几率，而这个冲突就会影响到我们的Hash表的效率。Hash算法我们将会设计一个普通的字符串Hash函数，在伪代码中表示如下：function hash(string, a, num_buckets): hash = 0 string_len = length(string) for i = 0, 1, …, string_len: hash += (a ** (string_len - (i+1))) * char_code(string[i]) hash = hash % num_buckets return hash这个Hash函数主要分为两步：将字符串转为大整型通过取余数mod m将整数的大小减小到固定范围变量a是一个素数，并且要大于英文字母，我们正在散列ASCII字符串，其字母大小为128，因此我们应该选择大于此的素数。char_code这个函数会返回字母对应的整数，使用的是ASCII中的字母。如下使用这个Hash函数：hash(“cat”, 151, 53)// 函数拆解hash = (1512 * 99 + 1511 * 97 + 151**0 * 116) % 53hash = (2257299 + 14647 + 116) % 53hash = (2272062) % 53hash = 5如果改变a我们会得到不同的结果：hash(“cat”, 163, 53) = 3代码实现// hash_table.cstatic int ht_hash(const char* s, const int a, const int m) { long hash = 0; const int len_s = strlen(s); for (int i = 0; i < len_s; i++) { hash += (long)pow(a, len_s - (i+1)) * s[i]; hash = hash % m; } return (int)hash;}什么是冲突？理想中的散列函数返回的结果都是均匀分布的，但是，对于任意一个散列函数，总会有一些输入经过散列后，得到相同的值。如果要找到这组输入，我们就需要测试大量的输入数据。因为上面提到的有不好的输入存在，意味着所有输入都没有完美的散列函数。所以在设计散列函数时，针对预期输入，我们的散列函数需要表现最好。不好的输入也存在安全问题，如果某个恶意用户向哈希表提供了一组冲突密钥，那么搜索这些密钥将比正常情况（O(1)）花费更长时间（O(n)）。这可以用作针对以哈希表为基础的系统（例如DNS和某些Web服务）的拒绝服务攻击。上一章：Hash table数据结构下一章：冲突处理 ...