散列一般也叫哈希。散列表也叫哈希表。本位将介绍散列表的基本知识、一致性哈希、哈希碰撞攻击及Java里的哈希实现。
介绍
散列表是普通数组概念的推广，在最坏情况下查找一个元素需要O(n)，在一些合理假设下，查找一个元素的期望时间为O(1)。
在散列表中，不是直接把关键字用作数组下标，而是根据关键字计算出下标。
散列函数：作用就是根据关键字计算出数组下标。
碰撞（collision）：多个关键字映射到同一个数组下标位置。
槽：一般把散列表的数组的一个存储单元（元素）叫做槽。
简单一致性散列：（Simple uniform hashing）假设任何元素散列到m个槽中的每一个的可能性是相同的，且与其他元素已被散列到什么位置上独立无关，这个假设称为简单一致性散列。