保定高端模板建站,网站首页qq在线咨询js,黃冈建设厅官方网站,百度快照如何优化1.hashMap底层实现
hashMap的实现我们是要分jdk 1.7及以下版本#xff0c;jdk1.8及以上版本
jdk 1.7 实现是用数组链表
jdk1.8 实现是用数组链表红黑树#xff0c; 链表长度大于8#xff08;TREEIFY_THRESHOLD#xff09;时#xff0c;会把链表转换为红黑树#xff0c…1.hashMap底层实现
hashMap的实现我们是要分jdk 1.7及以下版本jdk1.8及以上版本
jdk 1.7 实现是用数组链表
jdk1.8 实现是用数组链表红黑树 链表长度大于8TREEIFY_THRESHOLD时会把链表转换为红黑树红黑树节点个数小于6UNTREEIFY_THRESHOLD时才转化为链表防止频繁的转化
hashMap的一些常量
// 默认初始容量
DEFAULT_INITIAL_CAPACITY 16
// 数组默认最大的容量
DEFAULT_INITIAL_CAPACITY
当元素的总个数当前数组的长度 * 负载因子。数组会进行扩容扩容为原来的两倍
// 最大加载因子
DEFAULT_LOAD_FACTOR 0.75f;
链表树化阙值 默认值为 8 。表示在一个nodeTable节点下的值的个数大于8时候会将链表转换成为红黑树。
TREEIFY_THRESHOLD 8;
表示在进行扩容期间单个Node节点下的红黑树节点的个数小于6时候会将红黑树转化成为链表。
UNTREEIFY_THRESHOLD 6;
最小树化阈值当Table所有元素超过改值才会进行树化
MIN_TREEIFY_CAPACITY 64;
hash 带初始容量加载因子
public HashMap(int initialCapacity, float loadFactor) {if (initialCapacity 0)throw new IllegalArgumentException(Illegal initial capacity: initialCapacity);if (initialCapacity MAXIMUM_CAPACITY)initialCapacity MAXIMUM_CAPACITY;if (loadFactor 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException(Illegal load factor: loadFactor);this.loadFactor loadFactor;this.threshold tableSizeFor(initialCapacity);
}使用默认加载 因子
public HashMap() {this.loadFactor DEFAULT_LOAD_FACTOR; // all other fields defaulted
}hash 带初始容量
public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);
}转入一个map对象的构造器
public HashMap(Map? extends K, ? extends V m) {this.loadFactor DEFAULT_LOAD_FACTOR;putMapEntries(m, false);
}为什么建议设置HashMap的容量
HashMap有扩容机制就是当达到扩容条件时会进行扩容。扩容条件就是当HashMap中的元素个数超过临界值时就会自动扩容threshold loadFactor * capacity。
如果我们没有设置初始容量大小随着元素的不断增加HashMap会发生多次扩容。而HashMap每次扩容都需要重建hash表非常影响性能。所以建议开发者在创建HashMap的时候指定初始化容量。
扩容过程
下面HashMap的put方法, 首先hashMap 会通过hash 算法将key转换一个hash值如果key 为null ,hash值就为0如果不为null,先获取key的hashCode值然后将他将他与 与自己 hashCode值右移16位进行 异或运算。然后进入putVal方法 public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}static final int hash(Object key) {int h;return (key null) ? 0 : (h key.hashCode()) ^ (h 16);}
putVal方法’
putVal 首先判断当前hash数组是否有值当前table如果没有值就会进行扩容执行 resize()方法
判断当前节点是否有值如果有值就将当前的节点赋值给当前数组如果有就就判断当前的key的值
是否一样是一样的就将当前的value覆盖当前节点是红黑树就将节点加入到红黑树中
否则加入到链表中
然后判断当前数组大小是否大于扩容容量是的就扩容
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {NodeK,V[] tab; NodeK,V p; int n, i;if ((tab table) null || (n tab.length) 0)n (tab resize()).length;if ((p tab[i (n - 1) hash]) null)tab[i] newNode(hash, key, value, null);else {NodeK,V e; K k;if (p.hash hash ((k p.key) key || (key ! null key.equals(k))))e p;else if (p instanceof TreeNode)e ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value);else {for (int binCount 0; ; binCount) {if ((e p.next) null) {p.next newNode(hash, key, value, null);if (binCount TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))break;p e;}}if (e ! null) { // existing mapping for keyV oldValue e.value;if (!onlyIfAbsent || oldValue null)e.value value;afterNodeAccess(e);return oldValue;}}modCount;if (size threshold)resize();afterNodeInsertion(evict);return null;
}**resize方法**在初始化table或者在size超过threshold之后进行扩容执行resize方法
一.判断当前的数组长度是否是大于0如果大于0
1判断当前数组长度是否大于hashMap规定的最大值大于最大值将当前容器大小置为最大 值然后返回
2判断当前的数组是否数组长度扩大一倍是是否小于最大值并且大于默认初始容量就会将当前的容量大小threshold扩大一倍
二、如果当前初始过最大容量就用初始化的容量
三、否则就用默认使用默认初始容量DEFAULT_INITIAL_CAPACITY扩容容量为加载因子0.75默认初始容量
if (oldCap 0) {if (oldCap MAXIMUM_CAPACITY) {threshold Integer.MAX_VALUE;return oldTab;}else if ((newCap oldCap 1) MAXIMUM_CAPACITY oldCap DEFAULT_INITIAL_CAPACITY)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;newThr (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}判断当前扩容容量是否0如果为0就将扩容容量改为数组长度*加载因子
if (newThr 0) {float ft (float)newCap * loadFactor;newThr (newCap MAXIMUM_CAPACITY ft (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);
}创建hashMap的扩容后的数组判断旧的数组是否不为空遍历数组的每一个元素
(1)判断当前元素是否不是只有一个不是链表将当前hashMap取模存在hashMap数组里面
(2)判断当前是否为红黑树如果是红黑树就将红黑树赋给新数组
()判断当前是否为链表如果是链表就将链表赋给新数组
hreshold newThr;
SuppressWarnings({rawtypes,unchecked})NodeK,V[] newTab (NodeK,V[])new Node[newCap];
table newTab;
if (oldTab ! null) {for (int j 0; j oldCap; j) {NodeK,V e;if ((e oldTab[j]) ! null) {oldTab[j] null;if (e.next null)newTab[e.hash (newCap - 1)] e;else if (e instanceof TreeNode)((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;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;}}}}
}resize方法:全部代码
/***初始化或加倍表大小*如果为零则在中分配*符合字段阈值中保持的初始容量目标。*否则因为我们使用的是二次幂展开*每个垃圾箱中的物品必须保持在同一索引处或者移动*在新表格中偏移量为2的幂。**返回table*/final NodeK,V[] resize() {NodeK,V[] oldTab table;int oldCap (oldTab null) ? 0 : oldTab.length;int oldThr threshold;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)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;newThr (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;SuppressWarnings({rawtypes,unchecked})NodeK,V[] newTab (NodeK,V[])new Node[newCap];table newTab;if (oldTab ! null) {for (int j 0; j oldCap; j) {NodeK,V e;if ((e oldTab[j]) ! null) {oldTab[j] null;if (e.next null)newTab[e.hash (newCap - 1)] e;else if (e instanceof TreeNode)((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;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;
}2.扩容过程
1.8扩容机制当元素个数大于threshold时会进行扩容使用2倍容量的数组代替原有数组。采用尾插入的方式将原数组元素拷贝到新数组。1.8扩容之后链表元素相对位置没有变化而1.7扩容之后链表元素会倒置。
1.7链表新节点采用的是头插法这样在线程一扩容迁移元素时会将元素顺序改变导致两个线程中出现元素的相互指向而形成循环链表1.8采用了尾插法避免了这种情况的发生。
原数组的元素在重新计算hash之后因为数组容量n变为2倍那么n-1的mask范围在高位多1bit。在元素拷贝过程不需要重新计算元素在数组中的位置只需要看看原来的hash值新增的那个bit是1还是0是0的话索引没变是1的话索引变成“原索引oldCap”根据e.hash oldCap 0判断 。这样可以省去重新计算hash值的时间而且由于新增的1bit是0还是1可以认为是随机的因此resize的过程会均匀的把之前的冲突的节点分散到新的bucket。
3.解决hash冲突的办法有哪些HashMap用的哪种
虽然我们不希望发生冲突但实际上发生冲突的可能性仍是存在的。当关键字值域远大于哈希表的长度而且事先并不知道关键字的具体取值时。冲突就难免会发 生。另外当关键字的实际取值大于哈希表的长度时而且表中已装满了记录如果插入一个新记录不仅发生冲突而且还会发生溢出。因此处理冲突和溢出是 哈希技术中的两个重要问题。
解决hash冲突的办法链地址法、再哈希法、建立公共溢出区开放定址法
HashMap中采用的是 链地址法 。
法1链地址法 对于相同的哈希值使用链表进行连接。HashMap使用此法
优点
处理冲突简单无堆积现象。即非同义词决不会发生冲突因此平均查找长度较短 适合总数经常变化的情况。因为拉链法中各链表上的结点空间是动态申请的 占空间小。装填因子可取α≥1且结点较大时拉链法中增加的指针域可忽略不计 删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。 缺点
查询时效率较低。存储是动态的查询时跳转需要更多的时间 在key-value可以预知以及没有后续增改操作时候开放定址法性能优于链地址法。 不容易序列化 法2再哈希法 提供多个哈希函数如果第一个哈希函数计算出来的key的哈希值冲突了则使用第二个哈希函数计算key的哈希值。
优点
不易产生聚集 缺点
增加了计算时间 法3建立公共溢出区 将哈希表分为基本表和溢出表两部分凡是和基本表发生冲突的元素一律填入溢出表。
法4开放定址法 当关键字key的哈希地址p Hkey出现冲突时以p为基础产生另一个哈希地址p1若p1仍然冲突再以p为基础产生另一个哈希地址p2…直到找出一个不冲突的哈希地址pi 将相应元素存入其中。
4.使用的hash算法
Hash算法取key的hashCode值、高位运算、取模运算。
hkey.hashCode() //第一步 取hashCode值
h^(h16) //第二步 高位参与运算减少冲突
return h(length-1); //第三步 取模运算在JDK1.8的实现中优化了高位运算的算法通过hashCode()的高16位异或低16位实现的这么做可以在数组比较小的时候也能保证考虑到高低位都参与到Hash的计算中可以减少冲突同时不会有太大的开销。
5.为什么建议设置HashMap的容量
HashMap有扩容机制就是当达到扩容条件时会进行扩容。扩容条件就是当HashMap中的元素个数超过临界值时就会自动扩容threshold loadFactor * capacity。
如果我们没有设置初始容量大小随着元素的不断增加HashMap会发生多次扩容。而HashMap每次扩容都需要重建hash表非常影响性能。所以建议开发者在创建HashMap的时候指定初始化容量。
6.put方法流程
如果table没有初始化就先进行初始化过程使用hash算法计算key的索引判断索引处有没有存在元素没有就直接插入如果索引处存在元素则遍历插入有两种情况一种是链表形式就直接遍历到尾端插入一种是红黑树就按照红黑树结构插入链表的数量大于阈值8就要转换成红黑树的结构添加成功后会检查是否需要扩容
7.红黑树的特点
每个节点或者是黑色或者是红色。根节点和叶子节点NIL是黑色的。如果一个节点是红色的则它的子节点必须是黑色的。从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
8.在解决 hash 冲突的时候为什么选择先用链表再转红黑树?
因为红黑树需要进行左旋右旋变色这些操作来保持平衡而单链表不需要。所以当元素个数小于8个的时候采用链表结构可以保证查询性能。而当元素个数大于8个的时候并且数组容量大于等于64会采用红黑树结构。因为红黑树搜索时间复杂度是 O(logn)而链表是 O(n)在n比较大的时候使用红黑树可以加快查询速度。
9.HashMap 的长度为什么是 2 的幂次方
Hash 值的范围值比较大使用之前需要先对数组的长度取模运算得到的余数才是元素存放的位置也就是对应的数组下标。这个数组下标的计算方法是(n - 1) hash。将HashMap的长度定为2 的幂次方这样就可以使用(n - 1)hash位运算代替%取余的操作提高性能。
10.HashMap默认加载因子是多少为什么是 0.75
先看下HashMap的默认构造函数
int threshold; // 容纳键值对的最大值
final float loadFactor; // 负载因子
int modCount;
int size; Node[] table的初始化长度length为16默认的loadFactor是0.750.75是对空间和时间效率的一个平衡选择根据泊松分布loadFactor 取0.75碰撞最小。一般不会修改除非在时间和空间比较特殊的情况下
如果内存空间很多而又对时间效率要求很高可以降低负载因子Load factor的值 。如果内存空间紧张而对时间效率要求不高可以增加负载因子loadFactor的值这个值可以大于1。
11.一般用什么作为HashMap的key?
一般用Integer、String这种不可变类当 HashMap 当 key。String类比较常用。
因为 String 是不可变的所以在它创建的时候hashcode就被缓存了不需要重新计算。这就是 HashMap 中的key经常使用字符串的原因。获取对象的时候要用到 equals() 和 hashCode() 方法而Integer、String这些类都已经重写了 hashCode() 以及 equals() 方法不需要自己去重写这两个方法。
12.HashMap为什么线程不安全
多线程下扩容死循环。JDK1.7中的 HashMap 使用头插法插入元素在多线程的环境下扩容的时候有可能导致环形链表的出现形成死循环。在JDK1.8中在多线程环境下会发生数据覆盖的情况。
13.HashMap和HashTable的区别
HashMap和Hashtable都实现了Map接口。
HashMap可以接受为null的key和valuekey为null的键值对放在下标为0的头结点的链表中而Hashtable则不行。HashMap是非线程安全的HashTable是线程安全的。Jdk1.5提供了ConcurrentHashMap它是HashTable的替代。Hashtable很多方法是同步方法在单线程环境下它比HashMap要慢。哈希值的使用不同HashTable直接使用对象的hashCode。而HashMap重新计算hash值。
