Hash Table - HolmesJJ/Data-Structures-and-Algorithms GitHub Wiki
5分钟学会最经典的数据结构哈希表
带你快速理解 哈希表（散列表）的运作原理
9-4 哈希表
哈希表HashMap【数据结构和算法入门6】
数据结构 Hash表（哈希表）
哈希表（散列表）原理详解
散列表（哈希表）及其存储结构和特点详解
互联网公司面试经——你不得不知道的哈希表
Hash时取模一定要模质数吗
哈希表中数组的容量为什么是质数
哈希表——线性探测法、链地址法、查找成功、查找不成功的平均长度
哈希表针对冲突的两种方式优缺点是什么?
开放定址法——线性探测(Linear Probing)
数据结构与算法-哈希算法-Hash函数&装载因子&动态扩容
散列表(hash table)——算法导论(13)
关于平摊分析、表的扩增、势能分析初步理解
步骤1: 哈希结点HashNode
// 一个HashNode包括一对key和value
public class HashNode<K, V> {
private final K key;
private V value;
// 这里使用拉链法，需要使用LinkedList记录下一个结点
private HashNode<K, V> next;
// 这里使用开放寻址法（线性探测），需要使用isDeleted标记当前结点是被删除的结点
private final boolean isDeleted;
public HashNode(K key, V value) {
this.key = key;
this.value = value;
this.isDeleted = false;
}
public HashNode(boolean isDeleted) {
this.key = null;
this.value = null;
this.isDeleted = true;
}
public K getKey() {
return key;
}
public V getValue() {
return value;
}
public void setValue(V value) {
this.value = value;
}
public HashNode<K, V> getNext() {
return next;
}
public void setNext(HashNode<K, V> next) {
this.next = next;
}
public boolean isDeleted() {
return isDeleted;
}
}
步骤2: HashMap add(), get(), remove()
public class HashMap<K, V> {
// 定义哈希表扩容的临界值，需要根据实际情况调整
private final static double CRISIS = 0.7;
// 定义哈希表的桶数组
private ArrayList<HashNode<K, V>> bucketArray;
// 定义哈希表的桶的数量
private int numBuckets;
// 定义哈希结点HashNode的数量
private int size;
public HashMap() {
bucketArray = new ArrayList<>();
// 初始化桶的数量，需要根据实际情况调整
// 不能设置太小，否则哈希表会一直进行扩容的操作，性能下降
// 不能设置太大，否则会浪费内存空间
numBuckets = 10;
// 初始化哈希结点的数量为0
size = 0;
// 初始化桶的值
for (int i = 0; i < numBuckets; i++) {
bucketArray.add(null);
}
}
// 根据获取到的key，计算这个key的哈希值
// 这里的大前提是假设hashCode是唯一的，应该寻找更好的方法给不同的key计算唯一值
// 使用取模的操作计算这个key应该在哈希表的哪个桶里
private int getBucketIndex(K key) {
int hashCode = key.hashCode();
return hashCode % numBuckets;
}
// 添加一个键值对（拉链法）
public void add(K key, V value) {
// 获取哪个桶
int bucketIndex = getBucketIndex(key);
// 获取当前的这个桶的第一个哈希结点HashNode
HashNode<K, V> head = bucketArray.get(bucketIndex);
// 遍历这个链中的全部HashNode，看看是否有相同的key
// 这里的大前提是假设hashCode是唯一的，应该寻找更好的方法给不同的key计算唯一值
// 若有，替换这个key的值为新的值
while (head != null) {
// 比较两个key用hashCode比较
if (head.getKey().hashCode() == key.hashCode()) {
head.setValue(value);
return;
}
head = head.getNext();
}
// 若无，把新的值插入该链的头部（头插法）
head = bucketArray.get(bucketIndex);
HashNode<K, V> newHashNode = new HashNode<>(key, value);
newHashNode.setNext(head);
bucketArray.set(bucketIndex, newHashNode);
// 哈希结点+1
size++;
// 判断当前的哈希结点的数量是否已经占据了70%的桶，需要根据实际情况调整
if ((1.0 * size) / numBuckets >= CRISIS) {
generateBiggerBucketArray();
}
}
// 添加一个键值对（开放寻址法：线性探测）
public void add2(K key, V value) {
// 获取哪个桶
int bucketIndex = getBucketIndex(key);
// 获取当前的这个桶的第一个哈希结点HashNode
HashNode<K, V> head = bucketArray.get(bucketIndex);
// 判断这个桶的元素的HashNode，看看是否有相同的key
// 这里的大前提是假设hashCode是唯一的，应该寻找更好的方法给不同的key计算唯一值
// 若有，替换这个key的值为新的值
// 对于开放寻址法（线性探测），被标记为deleted的元素也被认为是null
while (head != null && !head.isDeleted()) {
// 比较两个key用hashCode比较
if (head.getKey().hashCode() == key.hashCode()) {
head.setValue(value);
return;
}
// 继续寻找下一个位置
bucketIndex++;
// 注意：如果遍历到尾部都没有找到空闲的位置，那么就再从表头开始找，直到找到为止
bucketIndex = bucketIndex % bucketArray.size();
head = bucketArray.get(bucketIndex);
}
// 若无，把新的值插入该桶中
HashNode<K, V> newHashNode = new HashNode<>(key, value);
bucketArray.set(bucketIndex, newHashNode);
// 哈希结点+1
size++;
// 判断当前的哈希结点的数量是否已经占据了70%的桶，需要根据实际情况调整
if ((1.0 * size) / numBuckets >= CRISIS) {
generateBiggerBucketArray();
}
}
// 生成一个更大的桶
private void generateBiggerBucketArray() {
// 把原来的桶数组临时存放
ArrayList<HashNode<K, V>> temp = bucketArray;
bucketArray = new ArrayList<>();
// 桶的数量扩大一倍
numBuckets = 2 * numBuckets;
// 初始化桶的值
for (int i = 0; i < numBuckets; i++) {
bucketArray.add(null);
}
// 把原来的桶的哈希头结点headNode移动到新的桶
// 注意位置会改变，因为numBuckets的改变会导致取模的值改变
for (HashNode<K, V> headNode: temp) {
while (headNode != null) {
add(headNode.getKey(), headNode.getValue());
// 这是个LinkedList，需要移动整个链
headNode = headNode.getNext();
}
}
}
// 根据key获取值（拉链法）
public V get(K key) {
// 获取哪个桶
int bucketIndex = getBucketIndex(key);
// 获取当前的这个桶的第一个哈希结点HashNode
HashNode<K, V> head = bucketArray.get(bucketIndex);
// 遍历这个链中的全部HashNode，看看是否有相同的key
// 这里的大前提是假设hashCode是唯一的，应该寻找更好的方法给不同的key计算唯一值
// 若有，则返回该值
while (head != null) {
// 比较两个key用hashCode比较
if (head.getKey().hashCode() == key.hashCode()) {
return head.getValue();
}
head = head.getNext();
}
// 若无，返回空值
return null;
}
// 根据key获取值（开放寻址法：线性探测）
public V get2(K key) {
// 获取哪个桶
int initialIndex = getBucketIndex(key);
int bucketIndex = initialIndex;
// 获取当前的这个桶的第一个哈希结点HashNode
HashNode<K, V> head = bucketArray.get(bucketIndex);
// 判断这个桶的元素的HashNode，看看是否有相同的key
// 这里的大前提是假设hashCode是唯一的，应该寻找更好的方法给不同的key计算唯一值
// 若有，则返回该值
while (head != null) {
// 对于开放寻址法（线性探测），被标记为deleted的元素会直接跳过
// 比较两个key用hashCode比较
if (!head.isDeleted() && head.getKey().hashCode() == key.hashCode()) {
return head.getValue();
}
// 继续寻找下一个位置
bucketIndex++;
if (initialIndex == bucketIndex) {
// 若循环一次都无，返回空值
return null;
}
// 注意：如果遍历到尾部都没有找到元素，那么就再从表头开始找，直到找到为止
bucketIndex = bucketIndex % bucketArray.size();
head = bucketArray.get(bucketIndex);
}
// 若无，返回空值
return null;
}
// 根据key删除一个哈希结点（拉链法）
public V remove(K key) {
// 获取哪个桶
int bucketIndex = getBucketIndex(key);
// 获取当前的这个桶的第一个哈希结点HashNode
HashNode<K, V> head = bucketArray.get(bucketIndex);
// LinkedList删除结点的方法（双指针法）
HashNode<K, V> prev = null;
// 遍历这个链中的全部HashNode，看看是否有相同的key
// 这里的大前提是假设hashCode是唯一的，应该寻找更好的方法给不同的key计算唯一值
// 若有，则跳出循环，并记录当前的结点位置
while (head != null) {
// 对于开放寻址法（线性探测），被标记为deleted的元素会直接跳过
// 比较两个key用hashCode比较
if (!head.isDeleted() && head.getKey().hashCode() == key.hashCode()) {
break;
}
prev = head;
head = head.getNext();
}
// 若无，则说明当前的key并没有对应的值，返回空值
if (head == null) {
return null;
}
// 若prev不为空，说明要删除的值不是桶的第一个值
if (prev != null) {
prev.setNext(head.getNext());
}
// 若prev为空，说明要删除的值刚好是桶的第一个值
else {
bucketArray.set(bucketIndex, head.getNext());
}
// 哈希结点-1
size--;
// 返回被删除的结点的值
return head.getValue();
}
// 根据key删除一个哈希结点（开放寻址法：线性探测）
// 对于删除操作稍微有些特别，不能单纯地把要删除的元素设置为空。
// 因为在查找的时候，一旦我们通过线性探测方法，找到一个空闲位置，我们就可以认定散列表中不存在这个数据。
// 但是，如果这个空闲位置是我们后来删除的，就会导致原来的查找算法失效。
// 这里我们可以将删除的元素，特殊标记为 deleted。
// 当线性探测查找的时候，遇到标记为 deleted 的空间，并不是停下来，而是继续往下探测。
public V remove2(K key) {
// 获取哪个桶
int initialIndex = getBucketIndex(key);
int bucketIndex = getBucketIndex(key);
// 获取当前的这个桶的第一个哈希结点HashNode
HashNode<K, V> head = bucketArray.get(bucketIndex);
// 判断这个桶的元素的HashNode，看看是否有相同的key
// 这里的大前提是假设hashCode是唯一的，应该寻找更好的方法给不同的key计算唯一值
// 若有，则跳出循环，并记录当前的结点位置
while (head != null) {
// 比较两个key用hashCode比较
if (head.getKey().hashCode() == key.hashCode()) {
break;
}
// 继续寻找下一个位置
bucketIndex++;
if (initialIndex == bucketIndex) {
// 若循环一次都无，返回空值
return null;
}
// 注意：如果遍历到尾部都没有找到元素，那么就再从表头开始找，直到找到为止
bucketIndex = bucketIndex % bucketArray.size();
head = bucketArray.get(bucketIndex);
}
// 若无，则说明当前的key并没有对应的值，返回空值
if (head == null) {
return null;
}
// 不能直接删除，应该将删除的元素，特殊标记为deleted
else {
bucketArray.set(bucketIndex, new HashNode<>(true));
}
// 哈希结点-1
size--;
// 返回被删除的结点的值
return head.getValue();
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
}
- HashMap和TreeMap的method都很像，均属于Java集合Map，但是HashMap没有与顺序相关的method
- HashMap是基于哈希表（符号表Symbol Table），TreeMap是基于红黑树（字典树Dictionary）
- Map<Key, Value>中所有的键值对的类型都是一致，例如Map<Integer, String>代表全部的key都是Integer，全部的value都是String
- 所有的key都不重复，若存在键值对key=1 value="abc"，若再插入key=1 value="def"，原来的值abc就会被覆盖
- containsValue效率不高，介于O(n)和O(n^2)之间，更接近于O(n)，取决于key的hash重合度，如果所有的value都分布于单独的key，则复杂度就是O(n)
- hashMap的get方法中会比较两个key的hash值和比较两个key是否相等，因此一定要Override hashCode()和equals()
public V get(Object key) {
if (key == null) return getForNullKey();
int hash = hash(key.hashCode());
for (Entry<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
Object k;
if (e.hash == hash &&((k = e.key) == key) || key.equals(k)))
return e.value;
}
return null;
}
| HashMap | TreeMap |
|---|---|
| containsKey | containsKey |
| containsValue | containsValue |
| entrySet | entrySet |
| get | get |
| isEmpty | isEmpty |
| keySet | keySet |
| put | put |
| putAll | putAll |
| remove | remove |
| values | values |
| ceilingEntry | |
| ceilingKey | |
| descendingKeySet | |
| firstEntry | |
| firstKey | |
| floorEntry | |
| floorKey | |
| headMap | |
| higherEntry | |
| higherKey | |
| ...(and more) |
TreeMap和HashMap的区别
HashMap与TreeMap的应用与区别
HashMap和TreeMap区别详解以及底层实现
Java TreeMap
Java HashMap
Integer
- hashCode始终是32位整数
- 每个32位整数都会获得唯一的hashCode
public static int hashCode(int value) {
return value;
}
Long
- long是64位，int是32位，而hash值是int类型，因此需要将64位转化为小于等于32位
- 让高位和低位都能够参与到hash运算中，让结果离散
- 核心逻辑：long的hash值是通过将前半段和后半段异或得到的
- 为什么XOR是组合哈希的默认方法？
public static int hashCode(long value) {
return (int)(value ^ (value >>> 32));
}
String
- 科普：为什么 String hashCode 方法选择数字31作为乘子
- 为什么Java String哈希乘数为31？
- 31是质数，且31 = 2^5 - 1
public static int hashCode(byte[] value) {
int h = 0;
int length = value.length >> 1;
for (int i = 0; i < length; i++) {
h = 31 * h + getChar(value, i);
}
return h;
}
好的哈希函数的两个属性：
-
对于每一个元素i，h(key，i)能够覆盖所有的存储桶
- 对于每个存储桶j，都有一些元素i使得：h(key，i) = j (元素均匀分布在每一个桶，因此哈希函数与哈希表的大小相关，注意扩容Grow和缩容Shrink)
- 哈希函数是{1...m}的全排列 (元素均匀分布在每一个桶，因此哈希函数与哈希表的大小相关，注意扩容Grow和缩容Shrink)
- 线性探测能够实现这点
-
均匀散列假设Simple Uniform Hashing Assumption
- 我们使用的哈希函数能够均匀并独立地将所有的键散布于0到M-1之间，散布方式为M!种（假设元素数量和桶的数量一致）
- 线性探测不能实现这点，例：对于有相同key的4个值A, B, C, D, 他们的散布方式只能是{A, B, C, D}, {B, C, D, A}, {C, D, A, B}, {D, A, B, C}，不符合上面的均匀并独立的要求
简单均匀散列假设Simple Uniform Hashing Assumption
若n为元素value的总数量，m是桶key的总数量
- 一个元素i被放在一个桶j的概率为P = 1/m（元素i只可能被放在其中一个桶j），此时桶j中的元素就会+1
- 一个元素i没有被放在一个桶j的概率1 - P = 1 - 1/m，此时桶j中的元素无变化
根据两点分布，可以得到一个元素i在一个桶j的分布列
| 元素i在桶j | 元素i不在桶j | |
|---|---|---|
| 桶j中的元素X | 1 | 0 |
| 概率P | 1/m | 1 - 1/m |
- 一个元素i被放在一个桶j的期望：E(X) = Pr(X == 1) * 1 + Pr(X == 0) * 0 = Pr(X == 1) = 1/m
- 一个桶中元素的期望（个数）= 对于n个元素，每个元素被放在一个桶中元素的期望（个数）的和 = nE(X) = n/m
- n/m是平均每个桶的元素数量，一般情况下n和m不会差很远，可以认为是O(1)
- 选择新的哈希表大小n并初始化
- 选择新的哈希函数h (好的哈希函数与哈希表的大小相关)
- 为原表中的每个元素通过新的哈希函数计算出新的位置，并储存到新的表中
- 初始化新的哈希表O(m2)
- 扫描旧的哈希表的每个元素O(m1)
- 把旧的哈希表中每个元素插入到新的哈希表O(1)，一共n个元素O(n)
- 时间复杂度是O(m1 + m2 + n)
- 扩容的时间复杂度是O(m1 + m2 + n) = O(n)
- 每次添加一个元素就要扩容一次，扩容的总时间复杂度是O(m1 + (m1 + 1) + (m1 + 2) + (m1 + 3) + ... + n) = O((n^2 - m^2)/2) = O(n^2)
- 扩容的时间复杂度是O(m1 + m2 + n) = O(m1 + 2*m1 + n) = O(n)
- 扩容的总时间复杂度是O(m1 + (m1 * 2^1) + (m1 * 2^2) + (m1 * 2^3) + ... + n)
- 假设初始哈希表大小m1 = 1（最坏情况），O(m1 + (m1 * 2^1) + (m1 * 2^2) + (m1 * 2^3) + ... + n) = O(2^0 + 2^1 + 2^2 + 2^3 + ... + n)(n = 2^k，k为扩容次数，因此k = logn，代入等比数列求和公式可得) = O(2n - 1) = O(n)
- 若第k-1次扩容2^(k-1) = n - 1（最坏情况，还差一个元素，但仍需要做一个扩容），此时扩容的总时间复杂度已接近O(n)，但仍需要一次扩容，而一次扩容的时间复杂度是O(n)，因此最终完成扩容的总时间复杂度仍是O(n)
- 扩容的时间复杂度是O(m1 + m2 + n) = O(m1 + m1^2 + n) = O(n^2)
- 扩容的总时间复杂度是O(m1 + (m1^2) + (m1^2)^2 + ... + n)
- 假设初始哈希表大小m1 = 2（最坏情况），O(m1 + (m1^2) + (m1^2)^2 + ... + n) = O(m1^(2^0) + m1^(2^1) + m1^(2^2) + ... + n)(n = m1^(2^k) = 2^(2^k)，k为扩容次数，因此k = logn，代入等比数列求和公式可得) = O(4n - 1) = O(n)，然而这只是第k次扩容后刚好为n的情况
- 若第k-1次扩容2^(k-1) = n - 1（最坏情况，还差一个元素，但仍需要做一个扩容），此时扩容的总时间复杂度已接近O(n)，但仍需要一次扩容，而一次扩容的时间复杂度是O(n^2)，因此最终完成扩容的总时间复杂度是O(n^2)
- 非常浪费空间
记帐法Accounting Method：想像有一个银行账户，算法的每步操作是向银行账户提钱
- 插入k个元素的开销
- 需要提出O(k)块钱用于扩容得到大小为k的哈希表
- 需要提出O(k)块钱用于插入元素到新的哈希表中
- 每步操作的总开销 = O(k + k) / k = O(1)
- 哈希表是符号表的一种
- key的位置是根据哈希函数计算出并固定的，不能随意变化
- 哈希冲突collision是无法避免的，对于值k1和k2，当h(k1) = h(k2)，就会产生冲突
- 好的哈希函数要符合上面提到的两个属性
- 一般假设哈希函数计算的时间复杂度为cost(h) = O(1)
-
若n为元素value的总数量，m是桶key的总数量，搜索（插入需要区分头插法还是尾插法）的时间复杂度是O(n/m + cost(h))
- 搜索最好和平均的时间复杂度是O(1 + cost(h))，即o(1)；使用拉链法Chaining时，当全部的值都存在同一个key的位置下，最差的时间复杂度是O(n + cost(h))
- 插入最好和平均的时间复杂度是O(1 + cost(h))，即o(1)；使用拉链法Chaining时，头插法最坏的时间复杂度是O(1 + cost(h))；尾插法最坏的时间复杂度是O(n + cost(h))
- 插入n个元素的期望最高时间复杂度是Θ(logn / loglogn)，等同于将n个球放进m = n个容器中，容器中最多有多少个球
-
拉链法总空间O(m + n)
- 表大小: m
- 链表大小: n
-
线性探测容易产“聚集Clusters”现象。当表中的第i、i+1、i+2的位置上已经存储某些关键字，则下一次哈希地址为i、i+1、i+2、i+3的关键字都将企图填入到i+3的位置上，这种多个哈希地址不同的关键字争夺同一个后继哈希地址的现象称为“聚集Clusters”
- 线性探测法一个很大的弊端就是当散列表中插入的数据越来越多时，散列冲突发生的可能性就会越来越大，空闲位置会越来越少，线性探测的时间就会越来越久。极端情况下，需要从头到尾探测整个散列表，所以最坏情况下的时间复杂度为O(n)
- 如果哈希表已满1/4，则将出现以下大小的“聚集Clusters”: θ(logn)
-
装载因子Load Factor是表示Hsah表中元素的填满的程度
- 若装载因子越大，填满的元素越多：好处是空间利用率高了；坏处是冲突的机会加大了
- 反之，若装载因子越小，填满的元素越少：好处是冲突的机会减小了；坏处是空间浪费多了
- 冲突的机会越大，则查找的成本越高；反之，查找的成本越小
- 因此，必须在“冲突的机会”与“空间利用率”之间寻找一种平衡与折衷