以前有记录过学习JDK HashMap源码，这次就记录下一个优秀的散列表实现需要的一些注意点

散列表的查询效率并不能笼统地说成是O(1)。它跟散列函数、装载因子、散列冲突等都有关系。如果散列函数设计得不好，或者装载因子过高，都可能导致散列冲突发生的概率升高，查询效率下降。

可能会出现的性能问题

在极端情况下，有些恶意的攻击者，还有可能通过精心构造的数据，使得所有的数据经过散列函数之后，都散列到同一个槽里。如果使用的是基于链表的冲突解决方法，那这个时候，散列表就会退化为链表，查询的时间复杂度就从O(1)急剧退化为O(n)。

如果散列表中有10万个数据，退化后的散列表查询的效率就下降了10万倍。更直接点说，如果之前运行100次查询只需要0.1秒，那现在就需要1万秒。这样就有可能因为查询操作消耗大量CPU或者线程资源，导致系统无法响应其他请求，从而达到拒绝服务攻击(DoS)的目的。这也就是散列表碰撞攻击的基本原理。

关于散列函数的设计

关于散列函数的设计，我们要尽可能让散列后的值随机且均匀分布，这样会尽可能地减少散列冲突，即便冲突之后，分配到每个槽内的数据也比较均匀。除此之外，散列函数的设计也不能太复杂，太复杂就会太耗时间，也会影响散列表的性能。

结合JDK HashMap的实现，总结了几个知识点

初始大小

JDK中HashMap默认的初始大小是16，当然这个默认值是可以设置的，如果事先知道大概的数据量有多大，可以通过修改默认初始大小，减少动态扩容的次数，这样会大大提高HashMap的性能。

装载因子和动态扩容

最大装载因子默认是0.75，当HashMap中元素个数超过0.75*capacity(capacity表示散列表的容量)的时候，就会启动扩容，每次扩容都会扩容为原来的两倍大小。

散列冲突解决方法

HashMap底层采用链表法来解决冲突。即使负载因子和散列函数设计得再合理，也免不了会出现拉链过长的情况，一旦出现拉链过长，则会严重影响HashMap的性能。

于是，在JDK1.8版本中，为了对HashMap做进一步优化，引入了红黑树。而当链表长度太长(默认超过8)时，链表就转换为红黑树。可以利用红黑树快速增删改查的特点，提高HashMap的性能。当红黑树结点个数少于8个的时候，又会将红黑树转化为链表。因为在数据量较小的情况下，红黑树要维护平衡，比起链表来，性能上的优势并不明显。

散列函数

散列函数的设计并不复杂，追求的是简单高效、分布均匀。还要结合实际数据来做分析，如关键字的长度、特点、分布、还有散列表的大小等。

下面是JDK HashMap的hash算法

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
在插入或查找的时候，计算Key被映射到桶的位置: 
int index = hash(key) & (capacity - 1)

JDK HashMap中hash函数的设计，确实很巧妙:

首先hashcode本身是个32位整型值，在系统中，这个值对于不同的对象必须保证唯一(JAVA规范)，这也是大家常说的，重写equals必须重写hashcode的重要原因。

获取对象的hashcode以后，先进行移位运算，然后再和自己做异或运算，即:hashcode ^ (hashcode >>> 16)，这一步甚是巧妙，是将高16位移到低16位，这样计算出来的整型值将“具有”高位和低位的性质

最后，用hash表当前的容量减去一，再和刚刚计算出来的整型值做位与运算。进行位与运算，很好理解，是为了计算出数组中的位置。但这里有个问题:

为什么要用容量减去一?

因为 A % B = A & (B - 1)，所以，(h ^ (h >>> 16)) & (capitity -1) = (h ^ (h >>> 16)) % capitity，可以看出这里本质上是使用了「除留余数法」

综上，可以看出，hashcode的随机性，加上移位异或算法，得到一个非常随机的hash值，再通过「除留余数法」，得到index，整体的设计过程与所说的“散列函数”设计原则非常吻合!

实际上，散列函数的设计方法还有很多，比如直接寻址法、平方取中法、折叠法、随机数法等