定义

散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展。可以说，没有数组，就没有散列表。

通过散列函数把元素的键值映射为数组下标，然后将数据存储在数组中对应下标的位置。
当我们按照键值查询元素时，使用同样的散列函数，将键值转换为数组下标，从对应的数组下标位置取数据。

散列表原理.png

散列表有两个非常关键的知识点

• 散列函数
• 散列冲突

散列函数

顾名思义，它是一个函数。hash(key)，入参是元素的key，返回为散列值也就是数组的下标。
所以就得到了散列函数的三个基本要求：

• 散列函数计算得到的散列值是一个非负整数
• 如果key1 == key2，那hash(key1) == hash(key2)
• 如果key1 != key2，那hash(key1) != hash(key2)
  前两个很好实现，第三个业界暂时没有一个完美的无冲突的散列函数，所以要通过其他途径来解决。这个途径就是解决散列冲突。

散列冲突

当不同的key通过散列函数，得到了同一个hash值，也就是说对应了数组的同一个下标，数组一个节点不可能存两个元素，所以要解决散列冲突。
通常有两种解决hash冲突的办法，开放寻址法和链表法。

• 开放寻址法就是：这个下标用不了了，就放他后面，他后面也有了，再往后找，直到找到。
• 链表法： 这个index里存不了一个数，那就存一个链表呗。

散列函数和hash冲突的具体用法，在后文会聊hashmap，linkedHashMap等应用的时候具体展开。

java hashMap

1、初始大小

HashMap默认的初始大小是16，当然这个默认值是可以设置的，可以通过修改默认大小，减少动态扩容的次数。

2、解决冲突解决方法

HashMap底层采用链表法来解决冲突。但链表过长，会退化成单链表，严重影响性能。JDK8版本中，为了对HashMap做进一步优化，引入了红黑树。当链表长度超过8时，链表就会转换成红黑树。利用红黑树快速增删改查的特性，提高HashMap的性能。当红黑树节点数量小于8个的时候，又会将红黑树转化为链表。

3、散列函数

hashMap的散列函数直接上代码，看似非常简单，实则非常精妙（涉及到位运算的通常都非常长精妙）

int hash(Object key) {
    int h = key.hashCode()；
    //capicity表示散列表的大小
    return (h ^ (h >>> 16)) & (capicity -1); 
}

先看h ^ (h >>> 16) 啥意思。因为int是32位的，让高16位 异或 低16位，增加高低位的参与度。
再看hash & (capicity - 1)。这段代码等价于 hash % capicity。为什么等价呢，因为capicity是2的整数倍(因为扩容是两倍两倍扩的, 你初始化大小为9, 内部也是开的大小也是16)，二进制与运算相当于取模。

4、装载因子和动态扩容

装载因子默认是0.75，当HashMap中元素个数超过 0.75 * 数组size 的时候，就会触发扩容，每次扩容都会扩容为原来的两倍大小。

扩容，扩的是数组的长度，那么数组上挂的一串一串的链表呢？
答案是：一个一个rehash，重新找自己在哪个数组下标下，然后重新生成链表(红黑树)。扩容非常耗时，但通过散列函数，rehash也是用一样的散列函数，因为扩容是2的整数倍，所以扩容后计算出的hash值，要么是在原位置，要么是在原位置再移动2次幂的位置，降低了计算的复杂度。

扩容有一个坑啊
这也是什么hashMap线程不安全的原因。有两种情况。
1、在put的时候。两个线程A和B，A hash完落到了数组1中，找到了数组1中的头结点。时间片用完。B hash完也落在数组1中，找到数组1中的头结点，并在后面插入了B的key-value。注意：这个时候，A和B获取的头结点是一样的。B操作完，A继续操作，使用同一个头结点，在尾巴上插入A的key-value。这个时候，B的值被覆盖了。
怎么避免呢？？在put的时候加锁就好了。
hashTable的做法是所有方法都加锁，使用synchronized，但并发太差，get也会加锁。
currentHashMap的做法是，将分成很多个map，每个map单独加锁，虽然在一个map中会有阻塞的情况，但其他的map不会阻塞。

2、1.7 在rehash的时候，链表可能会成环。1.8这个问题就没有了。

java LinkedHashMap

HashMap 底层是通过散列表这种数据结构实现的。而 LinkedHashMap 前面比 HashMap 多了一个“Linked”，这里的“Linked”是不是说，LinkedHashMap 是一个通过链表法解决散列冲突的散列表呢？实际上并没有这么简单。
先看下LinkedHashMap的特性：

LinkedHashMap是HashMap的一个子类，保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的，也可以在构造时带参数，按照访问次序排序。

先上个图

LinkedHashMap.png

从图中可以看到，linkedHashMap实际上时使用的散列表 + 双向链表实现的。

散列表：作用还是为了O(1)查找。从而实现O(1)插入和删除。
双向链表：可以看到不仅仅是双向链表，是"三向链表"
next指针: 和hashMap一致，是挂在数组上的链表，hash冲突时，往这个链表后面挂

before和after指针才是linkedHashMap的双端指针。目的是为了排序。hashMap无序，那就根据插入顺序或者LRU循序，用链表给无序的节点串起来不就有序了嘛。

这样get/put/remove根据散列表O(1)查询到节点。
遍历，根据头指针，遍历双向链表。

1、初始大小

同hashMap

2、 解决冲突办法

还是链表法。linkedHashMap就不升级成红黑树了。

3、散列函数

同hashMap

4、装载因子和动态扩容

装载因子同hashMap
扩容唯一不同的地方是，hashMap是遍历散列表，数组中一个下标一个下标遍历。
linkedHashMap是从头指针遍历双向链表。为啥呢，当然还是因为有序啊。