数据结构之散列表
散列表也叫作哈希表（hash table），这种数据结构提供了键（Key）和值（Value）的映射关系。只要给出一个Key，就可以高效查找到它所匹配的Value，时间复杂度接近于O(1)。
image.png
存储原理
哈希函数，散列表在本质上也是一个数组，散列表的Key是以字符串类型为主的，通过hash函数把Key和数组下标进行转换，作用是把任意长度的输入通过散列算法转换成固定类型、固定长度的散列值。
image.png
以Java为例：
//数组下标=取key的hashcode模数组的长度后的余数
index = HashCode (Key) % Array.length
int index=Math.abs("Hello".hashCode())%10; （0-9）
这是最简单的计算方式
还有很多hash函数：CRC16、CRC32、siphash 、murmurHash、times 33等
此种Hash计算方式为固定Hash方式，也称为传统Hash
该方式在数组固定时，可以快速检索
但当数组长度变化时，需要重新计算数组下标，此时根据key检索将出现问题
所以说传统Hash法虽然比较简单，但不利于扩展，如果要扩展可以采用一致性Hash法
操作
1）写操作（put）
写操作就是在散列表中插入新的键值对（在JDK中叫作Entry或Node） 第1步，通过哈希函数，把Key转化成数组下标
第2步，如果数组下标对应的位置没有元素，就把这个Entry填充到数组下标的位置。
image.png
2）Hash冲突（碰撞）
由于数组的长度是有限的，当插入的Entry越来越多时，不同的Key通过哈希函数获得的下标有可能是相同的，这种情况，就叫作哈希冲突。
image.png
解决哈希冲突的方法主要有两种：
开放寻址法
开放寻址法的原理是当一个Key通过哈希函数获得对应的数组下标已被占用时，就寻找下一个空档位置
image.png
在Java中，ThreadLocal所使用的就是开放寻址法
链表法
数组的每一个元素不仅是一个Entry对象，还是一个链表的头节点。每一个Entry对象通过next指针指向它的下一个Entry节点。当新来的Entry映射到与之冲突的数组位置时，只需要插入到对应的链表中即可，默认next指向null
image.png
在Entry中保存key和值，以及next指针
Entry{
int key;
Object value;
Entry next;
}
当根据key查找值的时候，在index=2的位置是一个单链表
遍历该单链表，再根据key即可取值
1）读操作（get）
读操作就是通过给定的Key，在散列表中查找对应的Value
第1步，通过哈希函数，把Key转化成数组下标
第2步，找到数组下标所对应的元素，如果key不正确，说明产生了hash冲突，
则顺着头节点遍历该单链表，再根据key即可取值
image.png
2）Hash扩容（resize）
散列表是基于数组实现的，所以散列表需要扩容
当经过多次元素插入，散列表达到一定饱和度时，Key映射位置发生冲突的概率会逐渐提高。这样一来，大量元素拥挤在相同的数组下标位置，形成很长的链表，对后续插入操作和查询操作的性能
都有很大影响
影响扩容的因素有两个
Capacity：HashMap的当前长度
LoadFactor：HashMap的负载因子（阈值），默认值为0.75f
当HashMap.Size >= Capacity×LoadFactor时，需要进行扩容
扩容的步骤：
- 扩容，创建一个新的Entry空数组，长度是原数组的2倍
-
重新Hash，遍历原Entry数组，把所有的Entry重新Hash到新数组中
image.png
关于HashMap的实现，JDK 8和以前的版本有着很大的不同。当多个Entry被Hash到同一个数组下标位置时，为了提升插入和查找的效率，HashMap会把Entry的链表转化为红黑树这种数据结构。
JDK1.8前在HashMap扩容时，会反序单链表，这样在高并发时会有死循环的可能
实现代码
package com.david.ds.hashmap;
/**
* 结点
*/
public class Node {
String key;
String value;
// 指向下一个结点
Node next;
public Node(String key, String value, Node next) {
this.key = key;
this.value = value;
this.next = next;
}
}
/**
* 单链表
*/
public class ListNode {
Node head; //头结点
/**
* 添加单链表结点
*
* @param key
* @param value
*/
public void addNode(String key, String value) {
//在外界设置好head了
if (head == null) return;
// 创建结点
Node node = new Node(key, value, null);
// 临时变量
Node tmp = head;
//循环单链表
while (true) {
//key相同覆盖值，从head开始
if (key.equals(tmp.key)) {
tmp.value = value;
}
if (tmp.next == null) {
break;
}
//指向下一个
tmp = tmp.next;
}
//在循环外挂载最后一个结点
tmp.next = node;
}
/**
* 获得值
*
* @param key
* @return
*/
public String getVal(String key) {
if (head == null) return null;
//只有一个结点
if (head.next == null) {
return head.value;
}
//遍历单链表
else {
Node tmp = head;
while (tmp != null) {
//找到匹配的key
if (key.equals(tmp.key)) {
return tmp.value;
}
//指向下一个
tmp = tmp.next;
}
return null;
}
}
}
/**
* 手动HashMap
*/
public class MyHashMap {
//数组初始化，2的n次方
ListNode[] map = new ListNode[8];
//ListNode的个数
int size;
final double factor = 0.75;
/**
* 设置值
* @param key
* @param value
*/
public void put(String key, String value) {
//该扩容了
if(size >= map.length * factor) {
System.out.println("map need resize");
return;
}
//计算索引数组下标
int index = Math.abs(key.hashCode()) % map.length;
//获得该下标处的ListNode
ListNode ln = map[index];
//该下标处无值
if (ln == null) {
//创建单链表
ListNode lnNew = new ListNode();
//创建头节点
Node head = new Node(key, value, null);
//挂载头节点
lnNew.head = head;
//把单链放到数组里
map[index] = lnNew;
size++;
}
//该下标有值，hash碰撞
else {
//单链表挂结点
ln.addNode(key, value);
}
}
/**
* 取值
* @param key
* @return
*/
public String get(String key) {
int index = Math.abs(key.hashCode()) % map.length;
ListNode ln = map[index];
if (ln == null) return null;
return ln.getVal(key);
}
public static void main(String[] args) {
MyHashMap hashMap = new MyHashMap();
hashMap.put();
hashMap.put();
hashMap.put();
System.out.println(hashMap.get("c1"));
}
}
时间复杂度
写操作： O(1) + O(m) = O(m) m为单链元素个数
读操作：O(1) + O(m) m为单链元素个数
Hash冲突写单链表：O(m)
Hash扩容：O(n) n是数组元素个数 rehash
Hash冲突读单链表：O(m) m为单链元素个数
优缺点
优点：读写快
缺点：哈希表中的元素是没有被排序的、Hash冲突、扩容 重新计算
应用
HashMap
JDK1.7中HashMap使用一个table数组来存储数据，用key的hashcode取模来决定key会被放到数组里的位置，如果hashcode相同，或者hashcode取模后的结果相同，那么这些key会被定位到Entry数组的同一个格子里，这些key会形成一个链表，在极端情况下比如说所有key的hashcode都相同，将会导致这个链表会很长，那么put/get操作需要遍历整个链表，那么最差情况下时间复杂度变为O（n）。
扩容死链
针对JDK1.7中的这个性能缺陷，JDK1.8中的table数组中可能存放的是链表结构，也可能存放的是红黑树结构，如果链表中节点数量不超过8个则使用链表存储，超过8个会调用treeifyBin函数，将链表转换为红黑树。那么即使所有key的hashcode完全相同，由于红黑树的特点，查找某个特定元素，也只需要O（logn）的开销。
image.png
字典
Redis字典dict又称散列表（hash），是用来存储键值对的一种数据结构。
Redis整个数据库是用字典来存储的。（K-V结构）
对Redis进行CURD操作其实就是对字典中的数据进行CURD操作。
Redis字典实现包括：字典(dict)、Hash表(dictht)、Hash表节点(dictEntry)。
image.png
布隆过滤器
布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机hash映射函数。
布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法。
image.png
布隆过滤器的原理是，当一个元素被加入集合时，通过K个Hash函数将这个元素映射成一个数组中的K个点，把它们置为1。检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了：如果这些点有任何一个0，则被检元素一定不在；如果都是1，则被检元素很可能在。这就是布隆过滤器的基本思想。
位图
Bitmap 的基本原理就是用一个 bit 来标记某个元素对应的 Value，而 Key 即是该元素。由于采用一个bit 来存储一个数据，因此可以大大的节省空间。
Java 中 int 类型占用 4 个字节，即 4 byte，又 1 byte = 8 bit，所以 一个 int 数字的表示大概如下:
image.png
试想以下，如果有一个很大的 int 数组，如 10000000，数组中每一个数值都要占用 4 个字节，则一共需要占用 10000000 * 4 = 40000000 个字节，即 40000000 / 1024.0 / 1024.0 = 38 M如果使用 bit 来存放上述 10000000 个元素，只需要 10000000 个 bit 即可， 10000000 / 8.0 / 1024.0/ 1024.0 = 1.19 M 左右，可以看到 bitmap 可以大大的节约内存。
使用 bit 来表示数组 [1, 2, 5] 如下所示，可以看到只用 1 字节即可表示：
image.png
