本文共 1935 字，大约阅读时间需要 6 分钟。

散列表

1. 散列表，数组演化而来，是将存储数据的键值，通过散列函数，转换成数组的下标，存储在数组中，这样通过键值查找数据时，只需根据散列函数，计算得到数组下标，进而得到存储数据；

2. 散列表，利用数组高效的按下标随机访问数据的特性，使其按照键值查找元素，简单的来说时间复杂度是 o( 1 )，但具体和散列冲突相关；

3. 散列函数的要求；

计算后的值是非负整数	如果 key1 == key2，要求 hash(key1) == hash(key2)	如果 key1 != key2，要求 hash(key1) 尽量不等于 hash(key2)，这样哈希冲突尽量少

4. 散列冲突，是指不同的 key，经过散列计算，得到相同的值，注意相同的 key，这不是散列冲突，这往往会覆盖之前存入的值，散列冲突往往无法避免，需要尽量减小冲突，出现冲突时，有开放寻址和链表法来解决；

开放寻址法：线下探测，二次探测和双重散列，是指发生冲突时，探测存储位置的方法，是顺序探测还是再次散列	线下探测：		插入元素：计算散列值后，发现该下标的数组元素已有值，那么依次向后查找直到有一个空闲位置，			在该空闲位置插入该元素		查找元素：计算散列之后，如果发现该下标元素，与要查找元素不等，那么依次向后查找，直到一个空闲位置，如果还没				有相等数据，就说明不存在该元素		删除元素：如果真实删除数据，可能导致查找失效，因此可以只标记为 delete

5. 当数组剩余空闲不多时，散列冲突会大大增加，使用装载因子来描述冲突情况，等于存储在表中的元素个数，除以散列表的长度，装载因子越大，表示冲突可能性越大；

6. 链表法，对于冲突元素，使用链表结构存储；

设计通用的散列表

1. 不合适的散列函数，会导致数据分布不均匀，导致查找性能低下；

2. 要求散列函数，计算简单，散列均匀，装载因子变大后，进行底层数组扩容，并将数据都重新进行散列存放；

如果扩容涉及数据特别多，一次性扩容时间不可接受，可以将扩容分批完成	当有新数据要插入时，将新数据插入到新散列表中，并从老散列表中拿出一个数据放入到新散列表	这样每新插入一个数据，都重复上面的过程，逐渐老散列表数据就都搬移到新散列表中	这个阶段的查找操作，需要现在新散列表中查找，如果没找到，在老散列表中查找

3. 采用开放寻址法解决哈希冲突，数据都存储在数组，对 cpu 缓存友好，序列化简单，但冲突后查找，插入代价比较高，适合小数据量，装载因子小的场景；

4. 链表法，可以接受更高的装载因子，内存利用率较高，缺点是 cpu 缓存不友好，指针会浪费一定空间，对于大对象，指针消耗可以忽略，当冲突大，链表长度长，可以使用红黑树，跳表代替链表，避免顺序查找，适合存储大对象、大数据量；

Java 中的 ThreadLocalMap 使用开放寻址法解决散列冲突	Java 中的 HashMap 使用链表法解决冲突	链表法更加普适

链表和散列表组合使用

1. LRU 缓存淘汰算法，之前链表实现，每次操作缓存，都需要先在链表中查找，查找时间复杂度是 o( n )，为此引入散列表，将链表节点都存储到散列表中，每个节点之间又通过 next，pre 组成双向链表，维护最近访问的顺序；

2. redis 的有序集合，元素有 score 和 key，value的属性，如果单纯用 score 组成一个跳表结构，使用区间的 score 查找比较高效，但是通过键值查找数据，就需要遍历整个链表，为此可以引入散列表，将链表节点按照 key 进行存储，使得按照 key 值查找元素非常高效；

3. LinkedHashMap，底层是散列表加链表，使得散列表中数据，维护了一个插入的顺序，并且维护访问顺序，和 LRU 实现一模一样；

put 操作，首先查找是否 key 相同，相同会先删除该节点，然后在链表尾部插入新值	get 操作，首先查找元素，然后移动元素到链表尾部		HashMap
   
     m = new LinkedHashMap<>(10, 0.75f, true);	m.put(3, 11);	m.put(1, 12);	m.put(5, 23);	m.put(2, 22);	m.put(3, 26);	m.get(5);	for (Map.Entry e : m.entrySet()) {
     		System.out.println(e.getKey());	}		// 3 1 5 2  --put(3.26)-- 1 5 2 3 -get(5)- 1 2 3 5
   

4. 通常散列表需要结合链表，是因为散列表是无序存储，如果需要维护某种顺序，就可以引入链表结构，来保证每次插入和删除元素，还是排序结构；

转载地址：http://msfin.baihongyu.com/