Java集合框架——HashTable源码1.7详解
程序员文章站
2022-05-12 10:57:14
...
一、HashTable
1.特点
键值都不能为空(否则会抛异常)
key不能重复
元素插入无序
2. 常用方法介绍
- synchronized int size() //元素总个数
- synchronized boolean isEmpty() //判断hashTable是否为空
- synchronizedboolean contains(Object value) //判断是否包含value值
- synchronized boolean containsKey(Object key) //判断是否包含key键
- synchronized V get(Object key) //通过key来进行获取值
- synchronized V put(K key, V value) //添加元素
- synchronized V remove(Object key) //删除元素
3.JDK1.7源码分析
-
继承关系
继承Dictionary,实现了Map,cloneable和Serializable(序列化)
public class Hashtable<K,V>extends Dictionary<K,V>implements Map<K,V>,
Cloneable, java.io.Serializable
-
底层数据结构
数组+链表 -
基本属性和默认值
transient Entry<K,V>[] table;//Entry类型的数组table
int count;//记录容量
int threshold; //扩容阈值
float loadFactor;//加载因子
transient int modCount = 0;//版本号
数组默认大小11
默认加载因子0.75
- 构造函数(4个)
1.public Hashtable(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal Load: "+loadFactor);
if (initialCapacity==0)
initialCapacity = 1;
this.loadFactor = loadFactor;
table = new Entry[initialCapacity];
threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
initHashSeedAsNeeded(initialCapacity);
}
- public Hashtable(int initialCapacity) {
this(initialCapacity, 0.75f);
}
- public Hashtable() {
this(11, 0.75f);
}
- public Hashtable(Map<? extends K, ? extends V> t) {
this(Math.max(2*t.size(), 11), 0.75f);
putAll(t);
}
-
增长方式
2+table.length+1 2倍 的数组的长度+1的 方式扩容
int newCapacity = (oldCapacity << 1) + 1; -
put()方法研究
public synchronized V put(K key, V value) {
//判断value是否为null,若为null,抛出空指针异常
if (value == null) {
throw new NullPointerException();
}
Entry tab[] = table;
//key不能为null,key为null也会抛出空指针异常
//通过key进行哈希,来获取到key该存储的索引位置
int hash = hash(key);
int index = (hash & 0x7FFFFFFF) % tab.length; //通过key的哈希,找到存储位置
//对索引位置的链表进行遍历,获取key是否存在(key存在条件,hash相等且通过key.equals判断相等)
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
V old = e.value;
e.value = value;
return old;
}
}
modCount++;
//扩容考虑 (Entry节点个数大于阈值)进行扩容,
if (count >= threshold) {
rehash();
tab = table;
hash = hash(key);
index = (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
Entry<K,V> e = tab[index];
tab[index] = new Entry<>(hash, key, value, e);
count++;
return null;
}
源码解析put()方法:
1.判断value是否为null,若为null,抛出空指针异常
2.通过key进行哈希,来获取到key该存储的索引位置
3.对索引位置的链表进行遍历,获取key是否存在
(key存在的条件:hash相等且通过key.equals判断相等)。
4.在存在key的情况下,将value值进行更新,且直接返回
5.key不存在则进行新节点插入逻辑。
5.1 扩容考虑:count>threshold(Entry节点个数大于阈值)进行扩容,
5.2 新容量的大小:2*table.length+1
5.3 将原来哈希表的所有元素进行重哈希到新的哈希表中
5.4 更新插入的key的新位置
5.5 找到新节点位置,创建Entry实体,通过头插法插入
4. hashTable保证线程安全原理:
hashTable在方法中添加Syncnized关键字,该关键字是一个互斥锁。目的是同一时刻只能有一个线程对资源进行访问
在hashMap中,对put,get等一般方法添加Syncnized关键字,修饰的是类对象,该对象调用put操作,即为该对象添加了一个
hashTable对象添加了一个互斥锁,同时只能有一个线程访问hashtable,从而保证添加元素不会出现异常。
底层操作系统提供的数组机制:从用户切换到内核态运行,当前的线程被阻塞住。
推荐阅读
-
Java自学-集合框架 HashMap和Hashtable的区别
-
Java集合框架详解(全)
-
Java源码解析——集合框架(四)——LinkedListLinkedList原码分析
-
Java源码解析——集合框架(二)——ArrayBlockingQueue
-
互联网架构-Java8集合框架源码分析-041:纯手写Jdk7HashMap集合框架
-
Java集合、多线程、反射和Spring框架总结,源码解析
-
互联网架构-Java8集合框架源码分析-040:LinkedList集合源码深度解析
-
Java集合框架之List ArrayList LinkedList使用详解刨析
-
Java集合框架之Stack Queue Deque使用详解刨析
-
Java基础之集合框架详解