数据结构之哈希表
-
在哈希表中进行添加，删除，查找等操作，性能十分之高，不考虑哈希冲突的情况下，仅需一次定位即可完成，时间复杂度为O(1)
-
数据结构的物理存储结构只有两种：
- 顺序存储结构
- 链式存储结构
-
哈希表的主干就是数组。对于数组通过指定下标的查找，时间复杂度为O(1)
-
查找的本质：存储位置 = f(关键字)，f是一个哈希函数
image
-
哈希冲突：但是，键是可能存在冲突的，相当于不同的键得出了相同的哈希值。HashMap即是采用了链地址法，也就是数组+链表的方式。
HashMap的结构
- HashMap的主干是一个Entry数组。
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
- Entry是HashMap中的一个静态内部类，它实现了一个链表结构。链表则是主要为了解决哈希冲突而存在的。
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;//存储指向下一个Entry的引用，单链表结构
int hash;//对key的hashcode值进行hash运算后得到的值，存储在Entry，避免重复计算
...
}
-
整体结构如下
image
- 解决的问题：哈希冲突
- 如果定位到的数组位置不含链表，即当前entry的next指向null，则一次查询即可。
- 如果定位到的数组包含链表
- 添加：O(1)，直接插入链表头部
- 查找：O(n)，遍历链表，key对象的equals方法逐一比对查找
HashMap的源码分析：插入
public V put(K key, V value) {
//其允许存放null的key和null的value，放在table[0]
if (key == null)
return putForNullKey(value);
int hash = hash(key);
//得到键的哈希值，用来获取数组中的索引
int i = indexFor(hash, table.length);
//如果i处的Entry不为null，则需要在链表中添加，但是添加前需要看是否已存在，存在返回旧值，不存在则最终addEntry。
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
//添加前看是否需要扩容
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
// 获取指定 bucketIndex 索引处的 Entry
Entry<K,V> e = table[bucketIndex];
// 将新创建的 Entry 放入 bucketIndex 索引处，并让新的 Entry 指向原来的 Entr
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
HashMap的源码分析：读取
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
final Entry<K,V> getEntry(Object key) {
int hash = (key == null) ? 0 : hash(key);
//通过哈希得到的index的e不为空则继续搜索链表
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 != null && key.equals(k))))
return e;
}
return null;
}
HashMap的性能参数
-
initialCapacity初始容量 -
transient int size;实际存储的key-value键值对的个数 -
int threshold;最大容量，threshold一般为 capacity*loadFactory，HashMap在进行扩容时需要参考threshold。初始容量默认为16 -
final float loadFactor;负载因子，代表了table的填充度有多少，默认是0.75，因此如果负载因子越大，对空间的利用更充分，然而后果是查找效率的降低；如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。 -
transient int modCount;用于防止多线程问题的快速失败。由于HashMap非线程安全，在对HashMap进行迭代时，如果期间其他线程的参与导致HashMap的结构发生变化了（比如put，remove等操作），在迭代过程中，判断modCount跟expectedModCount是否相等，如果不相等就表示已经有其他线程修改了Map，则需要抛出异常ConcurrentModificationException
HashMap的扩容
- HashMap数组的大小需要扩容时，原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。
- loadFactor的默认值为0.75。默认情况下，数组大小为16，那么当HashMap中元素个数超过160.75=12的时候，就把数组的大小扩展为 2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置。
- 这是一个非常消耗性能的操作，可以预设一个大小。
参考
- Java集合学习1：HashMap的实现原理，李大辉，http://tracylihui.github.io/2015/07/01/Java%E9%9B%86%E5%90%88%E5%AD%A6%E4%B9%A01%EF%BC%9AHashMap%E7%9A%84%E5%AE%9E%E7%8E%B0%E5%8E%9F%E7%90%86/
- HashMap实现原理及源码分析，dreamcatcher-cx，http://www.cnblogs.com/chengxiao/p/6059914.html
关于我：
linxinzhe，全栈工程师，目前供职于某500强通信企业。人工智能，区块链爱好者。
GitHub:https://github.com/linxinzhe
欢迎留言讨论，也欢迎关注我~
我也会关注你的哦！
网友评论