在对《Set和hashCode()》的一篇原创文章写完后，由于对自己的一些论断产生了模糊和怀疑，因此又对Set进行了一些研究，形成本篇。
在Set的使用场景中，我们不外乎看中了她存储数据的唯一性，即不能存储重复值，这在某些应用场合下是很必要的一个特性。那么从更深一层来考虑，Set究竟如何使数据不重复的呢？从另一个层面来考虑，她又如何确保在验证数据是否重复过程中的快速性呢？假设存储在Set中的数据有很多条，很普通的一个实现是每放入Set一个值value1，便提取Set中已有的多条数据跟该value1值进行对比，若相同，则不允许放入，反之则放入。运气好的话，迭代到几个元素之后便能够判断该值是否重复，否则，将会迭代所有已有的值。若是该Set中已经存储了上万条的数据，或者十几万条的数据？
一篇网文《Set是如何实现没有重复元素的？》一文给出了答案，该文内容翔实，说理性强，论据充分，是一篇难得的好文，在此感谢作者。尤其它指出了在Set的实现中，使用了Map的key唯一性来确保Set的值不重复(众所周知，Map中的key是唯一的)，有兴趣的可以去查看一下。
那么，Map中的key又是如何确保重复验证的快速性及key值的唯一性呢？
放心，这难不倒聪明的java的创造者们。他们巧妙地利用了Hash算法来实现并达到这一目的。 那么Hash又是什么？
Hash算法又称为散列算法，其实Hash算法产生的目的很单纯，其发明的目的是提高海量数据的查找速度。举个实例更能说明问题：
假设数据表中有N个无序的字符串（例如：中文人名），给你一个字符串，请迅速找到它在数据表中的序号。
最笨的方法是逐个比较的方式来查找。查找时间是O(N)，简单说最后的情况是比较N次。
hash表能够加快查找速度。使用hash表首先要申请一个定长的指针数组。通过在建立数据表时通过特定的计算公式（hash散列函数）计算出每个字符串对应的一个数值（就是将不固定长度的字符串转换成一个固定长度的数值或索引值）。而后把此数值作为数组下标，把此字符串在数据表的序号保存在此数组元素中（可以扩展到保存一个对象实例指针）。将来想查找某字符串对应位置时，只需要通过hash散列函数计算出字符串对应的值就可以直接知道此字符串的序号等信息了。
这样查找时间是O(1)了。因为不需要查找了，知道数组下标就能访问数组相应元素了，而元素中保存的就是序号等信息。
不妨给你一个直观的比方吧：
张三，给你个任务，你到山东省东营区去找一下一个叫做“李四”的人吧。张三很老实，说了声是就走了，三个月后回来，终于找着了那个叫做李四的人。他后来跟我们说，他采用了遍历的手法，即挨家挨户的去问，去找。
而将这个任务分配给王五的时候，王五说，老板，你给个确切的地址吧。老板说：山东省东营市东营区xx街道办事处xx社区xx号。结果不到一天时间，王五便找着了。
这也许就是hash查找算法与普通查找算法的区别。
通过查看HashMap的源代码证实，该HashMap确实采用了Hash算法来提高查找key的速度，并且使用了equals()来判断是否重复，有代码为证：
hash：
static int hash(int h) { h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } put: public V put(K key, V value) { if (key == null) return putForNullKey(value); int hash = hash(key.hashCode()); int i = indexFor(hash, table.length); for (Entry<</SPAN>K,V> e = table[i]; e != null;e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue =e.value; e.value =value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(hash, key, value, i); return null; } |
