【数据结构与算法之美】学习笔记 Day10 哈希表（Hash Table）的实现与特性
该文章用于记录哈希表的学习笔记
·
文章目录
一、哈希表（Hash Table）
哈希表，也叫散列表，根据键（Key）而直接访问在内存存储位置的数据结构，通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度
key-value 对，key 不重复
映射函数称做“哈希函数”，存放记录的数组称做“哈希表”或者“散列表”
映射的位置，即为哈希表的下标 Index
哈希表中不可能存储引用数据类型的对象数据，只是存储引用，即存储对象数据的地址
二、工程实践
- 电话号码簿
- 用户信息表
- 缓存（LRU Cache）
- 键值对存储（Redis）
三、Hash Function 哈希函数
散列表设计的关键
关键在于 hash 函数，设计好，冲突较少，能够让数值分散均匀，否则，较为集中，导致单链表太多，效率降低，时间复杂度由 O(1) 变为 O(n)
简单哈希函数
简单的哈希函数，把每一个字符，它的 ASCII 码加在一起，然后再 mod（取模）上一个数，最后的结果是多少就是多少
四、Hash Collisions 哈希冲突
散列表冲突的解决方法：拉链式解决冲突法
五、Java Map 实现
Map 定义
Java 中的 Map 定义为一个接口，接口就是定义一种能力，没有具体代码实现，具体实现交由子类完成
public interface Map<K,V>
常见子类
HashMap、TreeMap、HashTable、ConcurrentHashMap、LinkedHashMap、Properties
HashMap JDK 11 代码结构
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
......
}
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
......
}
TreeMap JDK 11 代码结构
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable{
private final Comparator<? super K> comparator;
private transient Entry<K,V> root;
......
}
Hashtable JDK 11 代码结构
public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable {
private transient Entry<?,?>[] table;
public synchronized V get(Object key) {
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return (V)e.value;
}
}
return null;
}
......
}
ConcurrentHashMap JDK 11 代码结构
public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
implements ConcurrentMap<K,V>, Serializable {
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
volatile V val;
volatile Node<K,V> next;
......
}
public V put(K key, V value) {
return putVal(key, value, false);
}
/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh; K fk; V fv;
if (tab == null || (n = tab.length) == 0)
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
break; // no lock when adding to empty bin
}
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else if (onlyIfAbsent // check first node without acquiring lock
&& fh == hash
&& ((fk = f.key) == key || (fk != null && key.equals(fk)))
&& (fv = f.val) != null)
return fv;
else {
V oldVal = null;
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key, value);
break;
}
}
}
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
else if (f instanceof ReservationNode)
throw new IllegalStateException("Recursive update");
}
}
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
......
}
LinkedHashMap JDK 11 代码结构
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>
{
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
transient LinkedHashMap.Entry<K,V> head;
transient LinkedHashMap.Entry<K,V> tail;
......
}
Properties JDK 11 代码结构
public class Properties extends Hashtable<Object,Object> {
private transient volatile ConcurrentHashMap<Object, Object> map;
......
}
Java 代码使用示例
- new HashMap() / new TreeMap()
- map.set(key, value)
- map.get(key)
- map.has(key)
- map.size()
- map.clear()
Python 代码使用示例
map_x = {
'jack': 100,
'张三': 80,
'Selina': 90,
......
}
参考
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
0
0- 0
已为社区贡献1条内容
所有评论(0)