网站导航栏代码,淘宝客建设网站需要哪些条件,网络营销与电子商务,海澜之家网站建设的计划哈希表的物理结构
HashMap底层都是哈希表#xff08;也称散列表#xff09;#xff0c;线程不安全#xff0c;其中维护了一个长度为2的幂次方的Entry类型的数组table#xff0c;数组的每一个索引位置被称为一个桶(bucket)#xff0c;你添加的映射关系(key,value)最终都被…哈希表的物理结构
HashMap底层都是哈希表也称散列表线程不安全其中维护了一个长度为2的幂次方的Entry类型的数组table数组的每一个索引位置被称为一个桶(bucket)你添加的映射关系(key,value)最终都被封装为一个Map.Entry类型的对象放到某个table[index]桶中。使用数组的目的是查询和添加的效率高可以根据索引直接定位到某个table[index]。 JDK8中HashMap结构如图
JDK7 HashMap分析
以JDK1.7.0_07为例其结构如图所示
1. Entry
key-value被封装为HashMap.Entry类型而这个类型实现了Map.Entry接口。
public class HashMapK,V{transient EntryK,V[] table;// 内部类static class EntryK,V implements Map.EntryK,V {final K key;V value;EntryK,V next; // 指向下一个Entryint hash; // 根据key计算出的哈希值2存储用以之后的添加等操作// 构造器Entry(int h, K k, V v, EntryK,V n) {value v;next n;key k;hash h;}//略}
}2. 属性
//table数组的默认初始化长度
static final int DEFAULT_INITIAL_CAPACITY 16;
//哈希表
transient EntryK,V[] table;
//哈希表中key-value键值对的个数
transient int size;
//临界值、阈值
int threshold;
//加载因子
final float loadFactor;
//默认加载因子0.75
static final float DEFAULT_LOAD_FACTOR 0.75f;
// 键值对数量上限2^30
static final int MAXIMUM_CAPACITY 1 30;3. 构造器
无参构造器
public HashMap() {//DEFAULT_INITIAL_CAPACITY默认初始容量16//DEFAULT_LOAD_FACTOR默认加载因子0.75this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}含参构造器
// 构造器
public HashMap(int initialCapacity, float loadFactor) {//校验initialCapacity合法性,[0,size)if (initialCapacity 0)throw new IllegalArgumentException(Illegal initial capacity: initialCapacity);//校验initialCapacity合法性 if (initialCapacity MAXIMUM_CAPACITY)initialCapacity MAXIMUM_CAPACITY;//校验loadFactor合法性if (loadFactor 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException(Illegal load factor: loadFactor);//计算得到table数组的长度保证capacity是2的整次幂int capacity 1;while (capacity initialCapacity)capacity 1; // 乘2//加载因子初始化为0.75this.loadFactor loadFactor;// threshold 初始为初始容量initialCapacity*加载因子dthreshold (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY 1);//初始化table数组table new Entry[capacity];useAltHashing sun.misc.VM.isBooted() (capacity Holder.ALTERNATIVE_HASHING_THRESHOLD);init(); // 该方法方法体为{}
}4. put
put方法基本步骤如下 put方法将(key1,value1)添加到当前hashmap的对象中首先会调用key1所在类的hashCode()方法计算key1的哈希值1此哈希值1再经过某种运算得到哈希值2。此哈希值2再经过某种运算(indexFor())才能确定在底层table数组中的索引位置i。 1如果数组索引为i上的数据为空则(key1,value1)直接添加成功 ------位置1 2如果数组索引为i上的数据不为空有(key2,value2)则需要进一步判断-----哈希冲突 此时需要进一步判断key1的哈希值2与key2的哈希值是否相同 3 如果哈希值不同则(key1,value1)直接添加成功 ------位置2 如果哈希值相同则需要继续调用key1所在类的equals()方法将key2放入equals()形参进行判断 4 equals方法返回false : 则(key1,value1)直接添加成功 ------位置3 equals方法返回true : 默认情况下value1会覆盖value2。
各位置说明 位置1直接将(key1,value1)以Entry对象的方式存放到table数组索引i的位置。 位置2和位置3(key1,value1) 与现有的元素以链表的方式存储在table数组索引i的位置新添加的元素指向旧添加的元素头插法。
… 在不断的添加的情况下满足如下条件的情况下会进行扩容: if ((size threshold) (null ! table[bucketIndex])) : threshold临界值-数组长度*加载因子数组长度默认值为16加载因子默认值为0.75 bucketIndex新添加的元素在table数组中的索引位置table[bucketIndex]在jdk7的条件下会新增链表 默认情况下当要添加的元素个数超过12(即数组的长度 * loadFactor得到的结果)时就要考虑扩容。 默认扩容长度为原数组长度的两倍
public V put(K key, V value) {// HashMap运行key和value为null//如果key是null单独处理存储到table[0]中如果有另一个key为nullvalue覆盖if (key null)return putForNullKey(value);/*hashCode值 xxxxxxxxxxtable.length-1 000001111hashCode值 xxxxxxxxxx 无符号右移几位和原来的hashCode值做^运算使得hashCode高位二进制值参与计算也发挥作用降低index冲突的概率。*/// 将key传入hash(),内部使用了key的哈希值1hashcode此方法执行结束后返回哈希值2int hash hash(key);// 计算新的映射关系应该存到table[i]位置// i hash table.length-1可以保证i在[0,table.length-1]范围内int i indexFor(hash, table.length);/*** 检查table[i]下面有没有key与已有的映射关系的key重复如果重复替换value* table[i]为null时直接跳过for循环添加新的映射关系* table[i]不为null时若存在已有的映射关系的key重复则新value覆盖原有value并返回原有value;若不存在则结束for循环添加新的映射关系*/for (EntryK,V e table[i]; e ! null; e e.next) {Object k;// 如果新增的key的哈希值2和键值对e的hash相等且两者key相等则进行覆盖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; // 添加返回null
}//如果key是null直接存入table[0]的位置
private V putForNullKey(V value) {//判断是否有重复的key如果有重复的就替换valuefor (EntryK,V e table[0]; e ! null; e e.next) {if (e.key null) {V oldValue e.value;e.value value;e.recordAccess(this);return oldValue;}}modCount; // 增删次数1//把新的映射关系存入[0]的位置而且key的hash值用0表示addEntry(0, null, value, 0);return null;
}// 哈希函数扰动函数,为了防止一些实现比较差的 hashCode() 方法,在key的hashcode的基础上进行无符号右移之后可以减少碰撞。
final int hash(Object k) {int h 0;if (useAltHashing) {if (k instanceof String) {return sun.misc.Hashing.stringHash32((String) k);}h hashSeed;}h ^ k.hashCode();// 无符号右移h ^ (h 20) ^ (h 12);return h ^ (h 7) ^ (h 4);
}// 根据哈希值和数组长度计算在table数组中的索引位置
static int indexFor(int h, int length) {// hash table.length-1可以保证i在[0,table.length-1]范围内return h (length-1);
}// 判断是否需要扩容然后新增key-value键值对
void addEntry(int hash, K key, V value, int bucketIndex) {//判断是否需要扩容//扩容1size达到临界值threshold2table[i]位置的链表非空if ((size threshold) (null ! table[bucketIndex])) {//table扩容为原来的2倍并且扩容后会重新调整所有key-value的存储位置resize(2 * table.length); // 重新计算得到新的key-value的hash和indexhash (null ! key) ? hash(key) : 0;bucketIndex indexFor(hash, table.length);}//存入table中createEntry(hash, key, value, bucketIndex);
}// 新增key-value键值对
void createEntry(int hash, K key, V value, int bucketIndex) {EntryK,V e table[bucketIndex];// 头插法进行插入table[bucketIndex] new Entry(hash, key, value, e);//个数增加size;
}5. get
public V get(Object key) {//key为null调用对应的getForNullKey方法if (key null)return getForNullKey();//当key ! null时去获得对应值 EntryK,V entry getEntry(key);//entry等于null说明没找到则返回null值return null entry ? null : entry.getValue(); }//key为null获取其对应的valueprivate V getForNullKey() {//key为null默认是放在哈希桶的第一个位置table[0]for (EntryK,V e table[0]; e ! null; e e.next) {if (e.key null)return e.value;}return null;} /*
① 计算key1的hash值调用方法hash(key1)
② 找index table.length-1 hash;
③ 如果table[index]不为空那么就挨个比较哪个Entry的key与它相同就返回它的value
*/ final EntryK,V getEntry(Object key) { if (size 0) { return null; } // 根据key值通过hash方法计算出对应的hash值int hash (key null) ? 0 : hash(key); // 根据hash值计算出对应的数组下标// 遍历 以该数组下标的数组元素为头结点的链表所有节点寻找该key对应的值for (EntryK,V e table[indexFor(hash, table.length)]; e ! null; e e.next) { Object k; // 若 hash值 key 相等则证明该Entry 就是要获取的键值对// 通过equals判断key是否相等if (e.hash hash ((k e.key) key || (key ! null key.equals(k)))) return e; } return null;
} 6. remove
/*
remove和get类似区别是在table[index]位置的链表删除key1为键的节点
① 计算key1的hash值用这个方法hash(key1)
② 找index table.length-1 hash;
③ 如果table[index]不为空那么就挨个比较如果哪个Entry的key与它相等就删除它把它前面的Entry的next的值修改为被删除Entry的next
*/
map.remove(key1);JDK8 HashMap分析
以JDK1.8.0_271为例其结构如图所示 key-value被封装为HashMap.Node类型或HashMap.TreeNode类型它俩都直接或间接的实现了Map.Entry接口。
存储到table数组的可能是Node结点对象也可能是TreeNode结点对象它们也是Map.Entry接口的实现类。即table[index]下的映射关系可能串起来一个链表或一棵红黑树。
1. Node
public class HashMapK,V{transient NodeK,V[] table;//Node类static class NodeK,V implements Map.EntryK,V {final int hash;final K key;V value;NodeK,V next;Node(int hash, K key, V value, NodeK,V next) {this.hash hash;this.key key;this.value value;this.next next;}// 其它结构略}//TreeNode类static final class TreeNodeK,V extends LinkedHashMap.EntryK,V {TreeNodeK,V parent;TreeNodeK,V left;TreeNodeK,V right;TreeNodeK,V prev;boolean red; //是红结点还是黑结点TreeNode(int hash, K key, V val, NodeK,V next) {super(hash, key, val, next);}}//....
}2. 属性
static final int DEFAULT_INITIAL_CAPACITY 1 4; // 默认的初始容量 16
static final int MAXIMUM_CAPACITY 1 30; //最大容量 1 30
static final float DEFAULT_LOAD_FACTOR 0.75f; //默认加载因子
static final int TREEIFY_THRESHOLD 8; //默认树化阈值8当链表的长度达到这个值后要考虑变为红黑树
static final int UNTREEIFY_THRESHOLD 6;//默认反树化阈值6当树中结点的个数达到此阈值后要考虑变为链表//当单个的链表的结点个数达到8并且table的长度达到64才会树化。
//当单个的链表的结点个数达到8但是table的长度未达到64会先扩容
static final int MIN_TREEIFY_CAPACITY 64; //最小树化容量64transient NodeK,V[] table; // 底层table数组
transient int size; //记录有效映射关系的对数也是Entry对象的个数
int threshold; //阈值当size达到阈值时考虑扩容
final float loadFactor; //加载因子影响扩容的频率3. 构造器
以下两个构造器初始化时并没有初始化table数组还是等到第一次执行put方法是才去初始化 无参构造器table数组
public HashMap() {this.loadFactor DEFAULT_LOAD_FACTOR; // all other fields defaulted (其他字段都是默认值)
}含参构造器
// 构造器
public HashMap(int initialCapacity, float loadFactor) {//校验initialCapacity合法性,[0,size)if (initialCapacity 0)throw new IllegalArgumentException(Illegal initial capacity: initialCapacity);//校验initialCapacity合法性 if (initialCapacity MAXIMUM_CAPACITY)initialCapacity MAXIMUM_CAPACITY;//校验loadFactor合法性if (loadFactor 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException(Illegal load factor: loadFactor);this.loadFactor loadFactor;// 初始容量暂时存放到 threshold 在resize中再赋值给 newCap 进行table初始化// HashMap 的容量必须是 2 的幂次方并且大于或等于指定的容量参数 initialCapacitythis.threshold tableSizeFor(initialCapacity);
}
4. put
// 计算哈希值
static final int hash(Object key) {
int h;
//如果key是nullhash是0
//如果key非null用key的hashCode值 与 key的hashCode值高16进行异或
//即就是用key的hashCode值高16位与低16位进行了异或的干扰运算
//JDK7索引计算格式: index hash table.length-1
//如果用key的原始的hashCode值与table.length-1 进行按位与那么基本上高16位没机会用上。
//这样就会增加冲突的概率为了降低冲突的概率把高16位加入到hash信息中。 return (key null) ? 0 : (h key.hashCode()) ^ (h 16);}public V put(K key, V value) { return putVal(hash(key), key, value, false, true);
}// 新增键值对
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {NodeK,V[] tab; //数组NodeK,V p; //一个结点int n, i; //n是数组的长度 i是下标//tab和table等, 如果table是空的if ((tab table) null || (n tab.length) 0){/*如果table是空的resize()完成了①创建了一个长度为16默认数组长度的数组②threshold 12 n 16*/n (tab resize()).length;}// i (n - 1) hash bucketIndex索引 数组长度-1 hash// 相对于jdk7的IndexFor()函数i (n - 1) hash根据哈希值2计算索引// if(pnull) 条件满足的话说明 table[i]为空没有节点if ((p tab[i (n - 1) hash]) null){//把新的映射关系直接放入table[i]作为链表的头结点tab[i] newNode(hash, key, value, null);}else {NodeK,V e; K k;//p是table[i]中第一个结点//if(table[i]的第一个结点与新的映射关系的key重复)if (p.hash hash ((k p.key) key || (key ! null key.equals(k))))e p;//用e记录这个table[i]的第一个结点后面进行value覆盖else if (p instanceof TreeNode){ //如果table[i]第一个结点是一个树结点//单独处理树结点//如果树结点中有key重复的就返回那个重复的结点用e接收即e!null//如果树结点中没有key重复的就把新结点放到树中并且返回null即enulle ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value);}else {//table[i]的第一个结点不是树结点也与新的映射关系的key不重复//binCount记录了table[i]下面的结点的个数for (int binCount 0; ; binCount) { // //如果p的下一个结点是空的说明当前的p是最后一个结点if ((e p.next) null) {//把新的结点连接到table[i]的最后p.next newNode(hash, key, value, null);//如果binCountTREEIFY_THRESHOLD-1 8-17该链表转红黑树的阈值if (binCount TREEIFY_THRESHOLD - 1) //要么扩容要么树化树化则还需要满足table数组长度大于等于MIN_TREEIFY_CAPACITY(64)treeifyBin(tab, hash);break;}//如果key重复了就跳出for循环此时e结点记录的就是那个key重复的结点if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))break;p e;//下一次循环ep.next就类似于ee.next往链表下移动}}//如果这个e不是null说明有key重复就考虑替换原来的valueif (e ! null) { // existing mapping for keyV oldValue e.value;if (!onlyIfAbsent || oldValue null)e.value value;afterNodeAccess(e); //什么也没干return oldValue;}}modCount; //元素个数增加//size达到阈值if (size threshold)resize(); //一旦扩容重新调整所有映射关系的位置afterNodeInsertion(evict); // 什么也没干return null;
}
// 数组扩容
final NodeK,V[] resize() {NodeK,V[] oldTab table; //oldTab原来的table//oldCap原来数组的长度int oldCap (oldTab null) ? 0 : oldTab.length;//oldThr原来的阈值int oldThr threshold;//最开始threshold是0//newCap新容量//newThr新阈值int newCap, newThr 0;if (oldCap 0) { //说明原来不是空数组if (oldCap MAXIMUM_CAPACITY) { //是否达到数组最大限制threshold Integer.MAX_VALUE;return oldTab;}else if ((newCap oldCap 1) MAXIMUM_CAPACITY oldCap DEFAULT_INITIAL_CAPACITY)//newCap 旧的容量*2 新容量最大数组容量限制//新容量32,64...//oldCap 初始容量16//新阈值重新算 2448 ....newThr oldThr 1; // double threshold}else if (oldThr 0) // initial capacity was placed in thresholdnewCap oldThr;else { // zero initial threshold signifies using defaultsnewCap DEFAULT_INITIAL_CAPACITY; //新容量是默认初始化容量16//新阈值 默认的加载因子 * 默认的初始化容量 0.75*16 12newThr (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}if (newThr 0) {float ft (float)newCap * loadFactor;newThr (newCap MAXIMUM_CAPACITY ft (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}threshold newThr; // 阈值赋值为新阈值1224.。。。//创建了一个新数组长度为newCap1632,64.。。SuppressWarnings({rawtypes,unchecked})NodeK,V[] newTab (NodeK,V[])new Node[newCap];table newTab;if (oldTab ! null) { //原来不是空数组//把原来的table中映射关系倒腾到新的table中for (int j 0; j oldCap; j) {NodeK,V e;if ((e oldTab[j]) ! null) {//e是table下面的结点oldTab[j] null; //把旧的table[j]位置清空if (e.next null) //如果是最后一个结点newTab[e.hash (newCap - 1)] e; //重新计算e的在新table中的存储位置然后放入else if (e instanceof TreeNode) //如果e是树结点//把原来的树拆解放到新的table((TreeNodeK,V)e).split(this, newTab, j, oldCap);else { // preserve orderNodeK,V loHead null, loTail null;NodeK,V hiHead null, hiTail null;NodeK,V next;//把原来table[i]下面的整个链表重新挪到了新的table中do {next e.next;if ((e.hash oldCap) 0) {if (loTail null)loHead e;elseloTail.next e;loTail e;}else {if (hiTail null)hiHead e;elsehiTail.next e;hiTail e;}} while ((e next) ! null);if (loTail ! null) {loTail.next null;newTab[j] loHead;}if (hiTail ! null) {hiTail.next null;newTab[j oldCap] hiHead;}}}}}return newTab;
}NodeK,V newNode(int hash, K key, V value, NodeK,V next) {//创建一个新结点return new Node(hash, key, value, next);
}
// 树化
final void treeifyBin(NodeK,V[] tab, int hash) {int n, index; NodeK,V e;//MIN_TREEIFY_CAPACITY最小树化容量64//如果table是空的或者 table数组的长度没有达到64if (tab null || (n tab.length) MIN_TREEIFY_CAPACITY)resize();//先扩容else if ((e tab[index (n - 1) hash]) ! null) {//用e记录table[index]的结点的地址TreeNodeK,V hd null, tl null;// do...while把table[index]链表的Node结点变为TreeNode类型的结点 do {TreeNodeK,V p replacementTreeNode(e, null);if (tl null)hd p;//hd记录根结点else {p.prev tl;tl.next p;}tl p;} while ((e e.next) ! null);//如果table[index]下面不是空if ((tab[index] hd) ! null)hd.treeify(tab);//将table[index]下面的链表进行树化}
} put执行过程如图所示
5. get public V get(Object key) {NodeK,V e;return (e getNode(hash(key), key)) null ? null : e.value;}// 查找final NodeK,V getNode(int hash, Object key) {NodeK,V[] tab; NodeK,V first, e; int n; K k;// table数组不为空且table[bucketIndex]第一个节点不为nullbucketIndex (n - 1) hash表示table数组的bucketIndex索引位置if ((tab table) ! null (n tab.length) 0 (first tab[(n - 1) hash]) ! null) { // key和first的哈希值相等且key与first的key相等if (first.hash hash // always check first node((k first.key) key || (key ! null key.equals(k))))return first; // 则table[bucketIndex]第一个节点就是我们要找到// 遍历table[bucketIndex]的所有节点if ((e first.next) ! null) {if (first instanceof TreeNode)// 如果是树节点则调用树的查找方法return ((TreeNodeK,V)first).getTreeNode(hash, key);// 否则为链表循环查找满足key和e的哈希值相等且key与e的key相等do {if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))return e;} while ((e e.next) ! null);}}return null;}6. remove public V remove(Object key) {NodeK,V e;return (e removeNode(hash(key), key, null, false, true)) null ?null : e.value;}final NodeK,V removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable) {NodeK,V[] tab; NodeK,V p; int n, index;// table数组不为空且table[bucketIndex]第一个节点不为nullbucketIndex (n - 1) hash表示table数组的bucketIndex索引位置即p指向table[bucketIndex]第一个节点if ((tab table) ! null (n tab.length) 0 (p tab[index (n - 1) hash]) ! null) {NodeK,V node null, e; K k; V v;// key和p的哈希值相等且key与p的key相等if (p.hash hash ((k p.key) key || (key ! null key.equals(k))))node p; // node记录p作为要删除的Nodeelse if ((e p.next) ! null) {if (p instanceof TreeNode)// 如果是树节点调用树的查找方法node ((TreeNodeK,V)p).getTreeNode(hash, key);else {// 否则为链表遍历比对do {// key和e的哈希值相等且key与e的key相等if (e.hash hash ((k e.key) key ||(key ! null key.equals(k)))) {node e; // node记录e作为要删除的Nodebreak;}p e; // p指向链表中要删除的e节点的上一个结点} while ((e e.next) ! null);}}// node不为null说明该key存在需要删除if (node ! null (!matchValue || (v node.value) value ||(value ! null value.equals(v)))) {if (node instanceof TreeNode)// 从红黑树中删除((TreeNodeK,V)node).removeTreeNode(this, tab, movable);else if (node p)// 从链表中删除e节点此时链表只有一个节点删除后tab[index]为nulltab[index] node.next;else// 从链表中删除此时链表有多个节点p.next node.next;modCount; // 修改次数1--size; // 键值对数量-1afterNodeRemoval(node); // 空return node;}}return null;}小结
①在jdk8中当我们创建了HashMap实例以后底层并没有像jdk7初始化长度为16的table数组。当首次执行put方法添加(key,value)时进行判断如果发现tablei尚未初始化则对数组进行初始化。 在jdk7中threshold 新容量capacity*负载因子loadFactor
threshold (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY 1);jdk8中threshold扩容时翻倍 jdk7和jdk8默认初始容量均为16扩容时默认扩容为2倍 ②jdk8中添加的key,value封装到了HashMap.Node类的对象中。而非jdk7中的HashMap.Entry。 ③ jdk8中新增的元素所在的索引位置如果有其他元素在经过一系列判断后如果能添加则是旧的元素指向新的元素而jdk7中的新的元素指向旧的元素。 简言之jdk8是类似尾插法链表情况jdk7类似头插法。 ④ jdk7时底层的数据结构是数组单向链表。 jdk8时底层的数据结构是数组单向链表红黑树。 红黑树出现的时机当某个索引位置i上的链表的长度达到8且数组的长度超过64时此索引位置上的元素要从单向链表改为红黑树。 红黑树进行put()/get()/remove()等操作时的时间复杂度为o(logn),相对于单向链表的时间复杂度O(n)性能更高。 static final int TREEIFY_THRESHOLD 8; 如果索引i位置是红黑树的结构当不断删除元素的情况下当前索引i位置上的元素的个数低于6时要从红黑树改为单向链表。 static final int UNTREEIFY_THRESHOLD 6;
JavaGuide HashMap底层源码分析
