女朋友问我HashTable内部结构是什么、扩容什么时候扩容的？
发布时间
阅读量：
阅读量
说明
有一天晚上、女朋友在床头问HashTable的内部结构是什么？扩容又是什么？
我：这都不知道？？？
女朋友： 不知道。
我：然后我就和她一顿说、先是这样在是那样给她解释清楚了......、说完就去睡觉了(后面是付费内容)......
好吧、我梦醒了、都是假的。
本章做一个HashTable的简单的总结、是jdk1.8版本的。
继承图
主要是做一些简单源码查看探究。
抛出问题
- 内部数据结构是怎么样的?
- 扩容机制是什么时候扩容的、扩容多少？
- key或value是否能为空。
- 是否线程安全?
HashMap集合说明
创建一个HashTable集合对象
Map<String,Integer> map = new HashTable<>();
复制代码
属性
// 存放数据的Entry数组
private transient Entry<?,?>[] table;
// Entry数组中有多少元素
private transient int count;
// 阈值用来做判断、是否需要扩容使用 threshold = 容量大小 * 负载系数
private int threshold; // 第一次默认为8
// 负载因子 = 负载系数
private float loadFactor;
//修改的次数
private transient int modCount = 0;
复制代码
构造器
/**
主要还是调用了这个构造
initialCapacity : 数据容量
loadFactor : 负载因子
*/
public Hashtable(int initialCapacity, float loadFactor) {
if (initialCapacity < 0) // 判断初始的容量是否小于0
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
if (loadFactor <= 0 || Float.isNaN(loadFactor))// 判断负载因子是否小于等于0和传递的参数值是否合法
throw new IllegalArgumentException("Illegal Load: "+loadFactor);
if (initialCapacity==0) // 数据容量是否等等于0
initialCapacity = 1; // 如果是赋值为1
this.loadFactor = loadFactor; // 负载因子
table = new Entry<?,?>[initialCapacity]; // 初始数组table的容量大小
// threshold = 容量大小 * （负载系数 = 负载因子）
threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}
// 自定义数组容量的构造
public Hashtable(int initialCapacity) {
this(initialCapacity, 0.75f);
}
// 无参构造
public Hashtable() {
this(11, 0.75f); // 它调用了一个有参构造
}
// 将另一个map集合的数据放入到Hashtable集合中
public Hashtable(Map<? extends K, ? extends V> t) {
this(Math.max(2*t.size(), 11), 0.75f);
putAll(t); // 这个方法做的事情就是遍历t集合的数据、调用Hashtable的put方法进行添加数据
}
复制代码
对集合CRUD简单说明
增
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) { // value 不能为null 否者抛出异常
throw new NullPointerException();
}
// 将构造中已经初始化的赋值给tab
Entry<?,?> tab[] = table;
// 计算hash值
int hash = key.hashCode();
// 计算下标
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
// 找到该下标中的节点链表
Entry<K,V> entry = (Entry<K,V>)tab[index];
// 遍历该链表下的节点
for(; entry != null ; entry = entry.next) {
// 判断hash值是否相同等、内容是否相等
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value; // 将旧的value值赋值给old
entry.value = value; // 将新的value值赋值给旧的value值
return old; // 将旧的value值返回
}
}
// 如果链表没有重复的则进行添加在其他位置上
addEntry(hash, key, value, index); // 后面来说这个方法
return null;
}
复制代码
问题:
获取Hash值 ：int hash = key.hashCode();
- 通过执行key对应类型实现的hashCode()方法获取对应的Hash值、没有实现则调用object类中的hashCode()来获取hash值、但是不能为null值会报空指针异常
获取下标：int index = (hash & 0x7FFFFFFF) % tab.length;
- 通过hash去取得一个下标
0x7FFFFFFF表示int类型最大的数2147483647、hash值按位与0x7FFFFFFF的结果取余tab数组的长度。
删
public synchronized V remove(Object key) {
Entry<?,?> tab[] = table; // 得到元素数组
int hash = key.hashCode(); // 算出Hash值
int index = (hash & 0x7FFFFFFF) % tab.length; // 算出下表
@SuppressWarnings("unchecked") // 抑制警告
// 获取改下标中的链表
Entry<K,V> e = (Entry<K,V>)tab[index];
for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) {
// 如果hash只相同、并且内容相同
if ((e.hash == hash) && e.key.equals(key)) {
modCount++;// 操作数++
if (prev != null) { // 如果遍历到链表有上一个节点的情况下成立
prev.next = e.next;
} else {
tab[index] = e.next; // 将下一个节点的数据给数组
}
count--; // 内容数量--
V oldValue = e.value; // 将下一个节点赋值、作为返回出去
e.value = null; //将null赋值给下一个节点
return oldValue; // 返回被移除的元素
}
}
return null; // 没有则返回null
}
复制代码
改
改和增加是一样的他也是、通过key的hash值来找到对应位置、将其对应值覆盖
查
public synchronized V get(Object key) {
Entry<?,?> tab[] = table; // 得到元素数组
int hash = key.hashCode(); // 算出Hash值
int index = (hash & 0x7FFFFFFF) % tab.length; // 算出下表
// 遍历链表
for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) { // hash 相同值相同成立
return (V)e.value; // 得到key对应的值、将其返回出去
}
}
return null; // 没有就返回null
}
复制代码
HashTable的核心内容扩容机制
扩容是在元素添加时、判断数组的大小是否能够存入下一个值、而做的操作扩容
----------------- 添加方法 ------------------
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) { // value 不能为null 否者抛出异常
throw new NullPointerException();
}
// 将构造中已经初始化的赋值给tab
Entry<?,?> tab[] = table;
// 计算hash值
int hash = key.hashCode();
// 计算下标
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
// 找到该下标中的节点链表
Entry<K,V> entry = (Entry<K,V>)tab[index];
// 遍历该链表下的节点
for(; entry != null ; entry = entry.next) {
// 判断hash值是否相同等、内容是否相等
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value; // 将旧的value值赋值给old
entry.value = value; // 将新的value值赋值给旧的value值
return old; // 将旧的value值返回
}
}
// 如果链表没有重复的则进行添加在其他位置上
addEntry(hash, key, value, index); // 后面来说这个方法
return null;
}
---------------addEntry()-----------------
private void addEntry(int hash, K key, V value, int index) {
modCount++; // 修改次数++
Entry<?,?> tab[] = table;
// 元素数量大于等于阈值进行扩容操作threshold 默认为8
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
rehash(); // 扩容主要方法
tab = table;
hash = key.hashCode();
index = (hash & 0x7FFFFFFF) % tab.length; // 扩容后重新计算索引下标
}
// Creates the new entry.
@SuppressWarnings("unchecked")
// 第一次这个节点为null
Entry<K,V> e = (Entry<K,V>) tab[index];
// 创建一个新的节点、赋值给tab[求出下标索引的位置上]
tab[index] = new Entry<>(hash, key, value, e);
count++; // 长度++
}
---------------rehash()-----------------
protected void rehash() {
int oldCapacity = table.length; // 先获取数组的长度
Entry<?,?>[] oldMap = table; // 获取数据
// overflow-conscious code
int newCapacity = (oldCapacity << 1) + 1; // 扩容成2倍+1
// 判断新扩容的容量大小是否超过默认的最大值
if (newCapacity - MAX_ARRAY_SIZE > 0) {
if (oldCapacity == MAX_ARRAY_SIZE)
// Keep running with MAX_ARRAY_SIZE buckets
return;
// 如果超过将最大值赋值给新容量
newCapacity = MAX_ARRAY_SIZE;
}
// newCapacity 获取到新容量的大小后创建一个最新容量大小的数组
Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
modCount++; // 修改次数++
// 计算新的threshold(阈值) 、 超过就进行扩容操作
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
table = newMap; // 重新给数组赋值
// 数据迁移遍历数据、将原来数组中的数据放到新数组中
for (int i = oldCapacity ; i-- > 0 ;) {
for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
Entry<K,V> e = old;
old = old.next;
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
e.next = (Entry<K,V>)newMap[index];
newMap[index] = e;
}
}
}
复制代码
小结： 扩容的条件count >= threshold、数组个数大于等于threshold(阈值)进行扩容操作、扩容操作改变数组的容量、以及阈值的大小。
解决问题
解决问题
- 内部数据结构是怎么样的?
1. 数组+链表 - 扩容机制是什么时候扩容的、扩容多少？
1. 在每次添加元素时判断count >= threshold处理则进行扩容、扩容是2倍加1 - key或value是否能为空。
1. 都不能为null
1. // key
2. int hash = key.hashCode(); // null.hashCode() 会抛出空指针异常
3. // value
4. if (value == null) { // value 不能为null 否者抛出异常
5. throw new NullPointerException();
6. }
7. 复制代码
- 是否线程安全?
- 是线程安全因为方法都用了
synchronized修饰
- 是线程安全因为方法都用了
其他信息
初始的信息有数组为11大小、threshold(阈值 = (容量大小*负载系数) )为8、loadFactor(负载系数)为0.75f、
HashTable添加元素时是采用头插法、就是将新元素添加在元素的头部。
右边的是添加第二值后的元素后的数据内存图
以上就是HashTable的简单说明。
有问题可以一起讨论。
作者：突突突突突
链接：https://juejin.cn/post/7005936004351672333
来源：掘金
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
全部评论 (0)
还没有任何评论哟~