抚顺建设网站,招标网免费,2015帝国cms网站,吗网站建设文章目录1. 常见的数据结构有三种结构1.1 各自数据结构的特点2. HashMap2.1 概述2.2 底层结构2.2.1 HashMa实现原理#xff1a;2.2.1.1 map.put(k,v)实现原理2.2.1.2 map.get(k)实现原理2.2.1.3 resize源码2.2.2 HashMap常用的变量2.2.3 HashMap构造函数2.3 JDK1.8之前存在的问…
文章目录1. 常见的数据结构有三种结构1.1 各自数据结构的特点2. HashMap2.1 概述2.2 底层结构2.2.1 HashMa实现原理2.2.1.1 map.put(k,v)实现原理2.2.1.2 map.get(k)实现原理2.2.1.3 resize源码2.2.2 HashMap常用的变量2.2.3 HashMap构造函数2.3 JDK1.8之前存在的问题2.4 HashMap红黑树原理3. 哈希表(散列)3.1 什么是哈希表3.2 什么是哈希冲突(面试题)3.3 解决哈希冲突的方法(面试题)(1) 开放地址法① 线性探查②二次探查③随机探查(2) 再哈希法(3) 链地址法(4)建立公共溢出区4. HashMap4.1 HashMap的hash()算法(面试)(1)为什么不是h key.hashCode()直接返回而要 h key.hashCode() ^ (h 16)来计算哈希值呢(2)为什么HashMap的初始容量和扩容都是2的次幂(3)如果指定了不是2的次幂的容量会发生什么4.2 HashMap为什么线程不安全(面试题)(1) 多线程下扩容造成的死循环和数据丢失(jdk1.7)(2)数据覆盖(jdk1.8)4.3 HashMap解决线程不安全(面试题)(1) 使用HashTable解决线程不安全问题(弃用)(2)HashMap和HashTable的区别(3)Collections.synchronizedMap(不常用)(4)ConcurrentHashMap(常用)4.4 为什么使用synchronized替换ReentrantLock锁呢4.5 HashMap底层 数组 链表 / 红黑树(面试题)(1)HashMap为什么引入链表(2)HashMap为什么引入红黑树(3)为什么不一开始就使用红黑树(4)说说你对红黑树的理解(5) 红黑树为什么要变色、左旋和右旋操作4.6 HashMap链表和红黑树转换(面试题)(1) 为什么链表长度大于8并且表的长度大于64的时候链表会转换成红黑树(2) 为什么转成红黑树是8呢而重新转为链表阈值是6呢(3) 为什么负载因子是0.754.6 HashMap扩容(面试题)(1)什么时候会发生扩容(2)为什么不是满了扩容(3)扩容过程1. 常见的数据结构有三种结构
数组结构链表结构哈希表结构
1.1 各自数据结构的特点
数组结构 存储区间连续、内存占用严重、空间复杂度大 优点随机读取和修改效率高原因是数组是连续的随机访问性强查找速度快缺点插入和删除数据效率低因插入数据这个位置后面的数据在内存中都要往后移动且大小固定不易动态扩展。 链表结构存储区间离散、占用内存宽松、空间复杂度小 优点插入删除速度快内存利用率高没有固定大小扩展灵活缺点不能随机查找每次都是从第一个开始遍历查询效率低 哈希表结构结合数组结构和链表结构的优点从而实现了查询和修改效率高插入和删除效率也高的一种数据结构
2. HashMap
2.1 概述
HashMap基于Map接口实现元素以键值对的方式存储并且允许使用NULL建和NULL值因为key允许重复因此只能有一个建为null另外HashMap不能保证放入元素的顺序它是无序的和放入的顺序并不能相同。HashMap是线程不安全的。
2.2 底层结构
HashMap底层采用哈希表结构JDK1.8之前为数组链表、JDK1.8之后为数组链表红黑树实现结合了数组和链表的优点 数组优点 通过数组下标可以快速实现对数组元素的访问效率极高 链表优点 插入或删除数据不需要移动元素只需修改节点引用效率极高。 HashMap内部使用数组存储数据数组中的每个元素类型为NodeK,V
//Node包含了四个字段hash、key、value、next其中next表示链表的下一个节点。
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;
}public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key value; }public final int hashCode() {return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final boolean equals(Object o) { if (o this) return true; if (o instanceof Map.Entry) { Map.Entry?,? e (Map.Entry?,?)o; if (Objects.equals(key, e.getKey()) Objects.equals(value, e.getValue())) return true; }return false;}
}2.2.1 HashMa实现原理
2.2.1.1 map.put(k,v)实现原理
1首先将k,v封装到Node对象当中节点。 2然后它的底层会调用k的hashCode()方法得出hash值。 3通过哈希表函数/哈希算法将hash值转换成数组的下标下标位置上如果没有任何元素就把Node添加到这个位置上。如果说下标对应的位置上有链表。此时就会拿着k和链表上每个节点的k进行equal。如果所有的equals方法返回都是false那么这个新的节点将被添加到链表的末尾。如其中有一个equals返回了true那么这个节点的value将会被覆盖。
put方法源码如下
//put方法会先调用一个hash()方法得到当前key的一个hash值
//用于确定当前key应该存放在数组的哪个下标位置
//这里的 hash方法我们姑且先认为是key.hashCode()其实不是的一会儿细讲
public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}//把hash值和当前的keyvalue传入进来
//这里onlyIfAbsent如果为true表明不能修改已经存在的值因此我们传入false
//evict只有在方法 afterNodeInsertion(boolean evict) { }用到可以看到它是一个空实现因此不用关注这个参数
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {NodeK,V[] tab; NodeK,V p; int n, i;//判断table是否为空如果空的话会先调用resize扩容if ((tab table) null || (n tab.length) 0)n (tab resize()).length;//根据当前key的hash值找到它在数组中的下标判断当前下标位置是否已经存在元素//若没有则把key、value包装成Node节点直接添加到此位置。// i (n - 1) hash 是计算下标位置的为什么这样算后边讲if ((p tab[i (n - 1) hash]) null)tab[i] newNode(hash, key, value, null);else { //如果当前位置已经有元素了分为三种情况。NodeK,V e; K k;//1.当前位置元素的hash值等于传过来的hash并且他们的key值也相等//则把p赋值给e跳转到①处后续需要做值的覆盖处理if (p.hash hash ((k p.key) key || (key ! null key.equals(k))))e p;//2.如果当前是红黑树结构则把它加入到红黑树 else if (p instanceof TreeNode)e ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value);else {//3.说明此位置已存在元素并且是普通链表结构则采用尾插法把新节点加入到链表尾部for (int binCount 0; ; binCount) {if ((e p.next) null) {//如果头结点的下一个节点为空则插入新节点p.next newNode(hash, key, value, null);//如果在插入的过程中链表长度超过了8则转化为红黑树if (binCount TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);//插入成功之后跳出循环跳转到①处break;}//若在链表中找到了相同key的话直接退出循环跳转到①处if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))break;p e;}}//①//说明发生了碰撞e代表的是旧值因此节点位置不变但是需要替换为新值if (e ! null) { // existing mapping for keyV oldValue e.value;//用新值替换旧值并返回旧值。if (!onlyIfAbsent || oldValue null)e.value value;//看方法名字即可知这是在node被访问之后需要做的操作。其实此处是一个空实现//只有在 LinkedHashMap才会实现用于实现根据访问先后顺序对元素进行排序hashmap不提供排序功能// Callbacks to allow LinkedHashMap post-actions//void afterNodeAccess(NodeK,V p) { }afterNodeAccess(e);return oldValue;}}//fail-fast机制modCount;//如果当前数组中的元素个数超过阈值则扩容if (size threshold)resize();//同样的空实现afterNodeInsertion(evict);return null;
}put方法通过hash函数计算key对应的哈希值hash函数源码如下
static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16);
}2.2.1.2 map.get(k)实现原理
(1)先调用k的hashCode()方法得出哈希值并通过哈希算法转换成数组的下标。 (2)通过上一步哈希算法转换成数组的下标之后在通过数组下标快速定位到某个位置上。如果这个位置上什么都没有则返回null。如果这个位置上有单向链表那么它就会拿着K和单向链表上的每一个节点的K进行equals如果所有equals方法都返回false则get方法返回null。如果其中一个节点的K和参数K进行equals返回true那么此时该节点的value就是我们要找的value了get方法最终返回这个要找的value。
get操作源码 public V get(Object key) {NodeK,V e;//如果节点为空则返回null否则返回节点的value。这也说明hashMap是支持value为null的。//因此我们就明白了为什么hashMap支持Key和value都为nullreturn (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;//首先要确保数组不能为空然后取到当前hash值计算出来的下标位置的第一个元素if ((tab table) ! null (n tab.length) 0 (first tab[(n - 1) hash]) ! null) {//若hash值和key都相等则说明我们要找的就是第一个元素直接返回if (first.hash hash // always check first node((k first.key) key || (key ! null key.equals(k))))return first;//如果不是的话就遍历当前链表或红黑树if ((e first.next) ! null) {//如果是红黑树结构则找到当前key所在的节点位置if (first instanceof TreeNode)return ((TreeNodeK,V)first).getTreeNode(hash, key);//如果是普通链表则向后遍历查找直到找到或者遍历到链表末尾为止。do {if (e.hash hash ((k e.key) key || (key ! null key.equals(k))))return e;} while ((e e.next) ! null);}}//否则说明没有找到返回nullreturn null;
}2.2.1.3 resize源码
通过put源码分析我们知道数组的初始化和扩容都是通过调用resize方法完成的
final NodeK,V[] resize() {//旧数组NodeK,V[] oldTab table;//旧数组的容量int oldCap (oldTab null) ? 0 : oldTab.length;//旧数组的扩容阈值注意看这里取的是当前对象的 threshold 值下边的第2种情况会用到。int oldThr threshold;//初始化新数组的容量和阈值分三种情况讨论。int newCap, newThr 0;//1.当旧数组的容量大于0时说明在这之前肯定调用过 resize扩容过一次才会导致旧容量不为0。//为什么这样说呢之前我在 tableSizeFor 卖了个关子需要注意的是它返回的值是赋给了 threshold 而不是 capacity。//我们在这之前压根就没有在任何地方看到过它给 capacity 赋初始值。if (oldCap 0) {//容量达到了最大值if (oldCap MAXIMUM_CAPACITY) {threshold Integer.MAX_VALUE;return oldTab;}//新数组的容量和阈值都扩大原来的2倍else if ((newCap oldCap 1) MAXIMUM_CAPACITY oldCap DEFAULT_INITIAL_CAPACITY)newThr oldThr 1; // double threshold}//2.到这里说明 oldCap 0并且 oldThr(threshold) 0这就是 map 初始化的时候第一次调用 resize的情况//而 oldThr的值等于 threshold此时的 threshold 是通过 tableSizeFor 方法得到的一个2的n次幂的值(我们以16为例)。//因此需要把 oldThr 的值也就是 threshold 赋值给新数组的容量 newCap以保证数组的容量是2的n次幂。//所以我们可以得出结论当map第一次 put 元素的时候就会走到这个分支把数组的容量设置为正确的值2的n次幂)//但是此时 threshold 的值也是2的n次幂这不对啊它应该是数组的容量乘以加载因子才对。别着急这个会在③处理。else if (oldThr 0) // initial capacity was placed in thresholdnewCap oldThr;//3.到这里说明 oldCap 和 oldThr 都是小于等于0的。也说明我们的map是通过默认无参构造来创建的//于是数组的容量和阈值都取默认值就可以了即 16 和 12。else { // zero initial threshold signifies using defaultsnewCap DEFAULT_INITIAL_CAPACITY;newThr (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}//③ 这里就是处理第2种情况因为只有这种情况 newThr 才为0//因此计算 newThr用 newCap即16 乘以加载因子 0.75得到 12 并把它赋值给 thresholdif (newThr 0) {float ft (float)newCap * loadFactor;newThr (newCap MAXIMUM_CAPACITY ft (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}//赋予 threshold 正确的值表示数组下次需要扩容的阈值此时就把原来的 16 修正为了 12。threshold newThr;SuppressWarnings({rawtypes,unchecked})//我们可以发现在构造函数时并没有创建数组在第一次调用put方法导致resize的时候才会把数组创建出来。这是为了延迟加载提高效率。NodeK,V[] newTab (NodeK,V[])new Node[newCap];table newTab;//如果原来的数组不为空那么我们就需要把原来数组中的元素重新分配到新的数组中//如果是第2种情况由于是第一次调用resize此时数组肯定是空的因此也就不需要重新分配元素。if (oldTab ! null) {//遍历旧数组for (int j 0; j oldCap; j) {NodeK,V e;//取到当前下标的第一个元素如果存在则分三种情况重新分配位置if ((e oldTab[j]) ! null) {oldTab[j] null;//1.如果当前元素的下一个元素为空则说明此处只有一个元素//则直接用它的hash()值和新数组的容量取模就可以了得到新的下标位置。if (e.next null)newTab[e.hash (newCap - 1)] e;//2.如果是红黑树结构则拆分红黑树必要时有可能退化为链表else if (e instanceof TreeNode)((TreeNodeK,V)e).split(this, newTab, j, oldCap);//3.到这里说明这是一个长度大于 1 的普通链表则需要计算并//判断当前位置的链表是否需要移动到新的位置else { // preserve order// loHead 和 loTail 分别代表链表旧位置的头尾节点NodeK,V loHead null, loTail null;// hiHead 和 hiTail 分别代表链表移动到新位置的头尾节点NodeK,V hiHead null, hiTail null;NodeK,V next;do {next e.next;//如果当前元素的hash值和oldCap做与运算为0则原位置不变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.2.2 HashMap常用的变量
//默认的初始化容量为16必须是2的n次幂
static final int DEFAULT_INITIAL_CAPACITY 1 4; // aka 16//最大容量为 2^30
static final int MAXIMUM_CAPACITY 1 30;//默认的加载因子0.75乘以数组容量得到的值用来表示元素个数达到多少时需要扩容。
//为什么设置 0.75 这个值呢简单来说就是时间和空间的权衡。
//若小于0.75如0.5则数组长度达到一半大小就需要扩容空间使用率大大降低
//若大于0.75如0.8则会增大hash冲突的概率影响查询效率。
static final float DEFAULT_LOAD_FACTOR 0.75f;//刚才提到了当链表长度过长时会有一个阈值超过这个阈值8就会转化为红黑树
static final int TREEIFY_THRESHOLD 8;//当红黑树上的元素个数减少到6个时就退化为链表
static final int UNTREEIFY_THRESHOLD 6;//链表转化为红黑树除了有阈值的限制还有另外一个限制需要数组容量至少达到64才会树化。
//这是为了避免数组扩容和树化阈值之间的冲突。
static final int MIN_TREEIFY_CAPACITY 64;//存放所有Node节点的数组
transient NodeK,V[] table;//存放所有的键值对
transient SetMap.EntryK,V entrySet;//map中的实际键值对个数即数组中元素个数
transient int size;//每次结构改变时都会自增fail-fast机制这是一种错误检测机制。
//当迭代集合的时候如果结构发生改变则会发生 fail-fast抛出异常。
transient int modCount;//数组扩容阈值
int threshold;//加载因子
final float loadFactor; //普通单向链表节点类
static class NodeK,V implements Map.EntryK,V {//key的hash值put和get的时候都需要用到它来确定元素在数组中的位置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;}
}//转化为红黑树的节点类
static final class TreeNodeK,V extends LinkedHashMap.EntryK,V {//当前节点的父节点TreeNodeK,V parent; //左孩子节点TreeNodeK,V left;//右孩子节点TreeNodeK,V right;//指向前一个节点TreeNodeK,V prev; // needed to unlink next upon deletion//当前节点是红色或者黑色的标识boolean red;TreeNode(int hash, K key, V val, NodeK,V next) {super(hash, key, val, next);}//返回当前节点的根节点final TreeNodek,v root() {for (TreeNodek,v r this, p;;) {if ((p r.parent) null)return r;r p;}}
} 2.2.3 HashMap构造函数
HashMap有四个构造函数可供我们使用
//默认无参构造指定一个默认的加载因子
public HashMap() {this.loadFactor DEFAULT_LOAD_FACTOR;
}//可指定容量的有参构造但是需要注意当前我们指定的容量并不一定就是实际的容量下面会说
public HashMap(int initialCapacity) {//同样使用默认加载因子this(initialCapacity, DEFAULT_LOAD_FACTOR);
}//可指定容量和加载因子但是笔者不建议自己手动指定非0.75的加载因子
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;//这里就是把我们指定的容量改为一个大于它的的最小的2次幂值如传过来的容量是14则返回16//注意这里按理说返回的值应该赋值给 capacity即保证数组容量总是2的n次幂为什么这里赋值给了 threshold 呢//先卖个关子等到 resize 的时候再说this.threshold tableSizeFor(initialCapacity);
}//可传入一个已有的map
public HashMap(Map? extends K, ? extends V m) {this.loadFactor DEFAULT_LOAD_FACTOR;putMapEntries(m, false);
}//把传入的map里边的元素都加载到当前map
final void putMapEntries(Map? extends K, ? extends V m, boolean evict) {int s m.size();if (s 0) {if (table null) { // pre-sizefloat ft ((float)s / loadFactor) 1.0F;int t ((ft (float)MAXIMUM_CAPACITY) ?(int)ft : MAXIMUM_CAPACITY);if (t threshold)threshold tableSizeFor(t);}else if (s threshold)resize();for (Map.Entry? extends K, ? extends V e : m.entrySet()) {K key e.getKey();V value e.getValue();//put方法的具体实现后边讲putVal(hash(key), key, value, false, evict);}}
}tableSizeFor() 上边的第三个构造函数中调用了 tableSizeFor 方法这个方法是怎么实现的呢
static final int tableSizeFor(int cap) {int n cap - 1;n | n 1;n | n 2;n | n 4;n | n 8;n | n 16;return (n 0) ? 1 : (n MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n 1;
}可以看到这个方法是针对整型数据进行的操作 int n cap - 1; 不知道为什么要减去1实际上这只是针对二的整数幂进行的退位操作
先单独看这段代码 假设 n 5时n | n 1;0000 01010000 00100000 0111n | n 2;0000 01110000 00010000 0111n | n 4;0000 01110000 00000000 0111...最后无符号右移再或等结果都是0000 0111这样就得到了5最高非0位下的最大值即 0000 0111对其加一的结果就是 0000 1000即大于5的最小二的整数幂 8其实这个算法的思路就是将该数字的最高非0位后面全置为1其利用了“拷贝”的方式 n ; 1000 0000 0000 0000 0000 0000 0000 0000
n | n 1; 1100 0000 0000 0000 0000 0000 0000 0000 将最高位拷贝到下1位
n | n 2; 1111 0000 0000 0000 0000 0000 0000 0000 将上述2位拷贝到紧接着的2位
n | n 4; 1111 1111 0000 0000 0000 0000 0000 0000 将上述4位拷贝到紧接着的4位
n | n 8; 1111 1111 1111 1111 0000 0000 0000 0000 将上述8位拷贝到紧接着的8位
n | n 16; 1111 1111 1111 1111 1111 1111 1111 1111 将上述16位拷贝到紧接着的16位由上面可以看出其通过这五次的计算最后的结果刚好可以填满32位的空间也就是一个int类型的空间这就是为什么必须是int类型且最多只无符号右移16位 return (n 0) ? 1 : (n MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n 1;其中的MAXIMUM_CAPACITY 是HashMap的最大空间为1 30即2^30刚好一个G所以HashMap大小不是取决于堆内存
为什么要减一 以 n 8为例0000 1000最后的结果为0000 1111对其加一得到的是16显然没有把自身包含进去若减一n 70000 0111最后的结果为0000 0111对其加一得到的是8所以在一开始进行减一的操作是为了防止出现二的整数幂时没有把自身包含进范围
2.3 JDK1.8之前存在的问题
JDK1.8之前HashMap底层实现用的是数组链表。JDK1.8以后用数组链表红黑树。
HashMap通过hash方法计算key的哈希码然后通过n-1hash 公式n为数组长度,初始化数组默认长度为16得到key在数组中存放的下标。
当两个key在数组中存在的下标一致时哈希冲突哈希碰撞数据将以链表的方式存储。
在链表中查找数据必须从第一个元素开始一层一层往下找直到找到为止时间复杂度为O(N)所以当链表长度越来越长时HashMap的效率越来越低。
2.4 HashMap红黑树原理
红黑树除了插入操作慢其他操作都比链表快当hash表的单一链表长度超过 8 个的时候数组长度大于64链表结构就会转为红黑树结构。当红黑树上的节点数量小于6个会重新把红黑树变成单向链表数据结构。 为什么要这样设计呢好处就是避免在最极端的情况下链表变得很长很长在查询的时候效率会非常慢。
红黑树查询其访问性能近似于折半查找时间复杂度 O(logn)链表查询这种情况下需要遍历全部元素才行时间复杂度 O(n)
简单的说红黑树是一种近似平衡的二叉查找树其主要的优点就是“平衡“即左右子树高度几乎一致以此来防止树退化为链表通过这种方式来保障查找的时间复杂度为 log(n)。 关于红黑树的内容网上给出的内容非常多主要有以下几个特性 1、每个节点要么是红色要么是黑色但根节点永远是黑色的 2、每个红色节点的两个子节点一定都是黑色 3、红色节点不能连续也即是红色节点的孩子和父亲都不能是红色 4、从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点 5、所有的叶子节点都是是黑色的注意这里说叶子节点其实是上图中的 NIL 节点在树的结构发生改变时插入或者删除操作往往会破坏上述条件 3 或条件 4需要通过调整使得查找树重新满足红黑树的条件。
3. 哈希表(散列)
3.1 什么是哈希表 根据关键码值(Key value)而直接进行访问的数据结构。也就是说它通过把关键码值映射到表中一个位置来访问记录以加快查找的速度。这个映射函数叫做散列函数存放记录的数组叫做散列表。 给定表M存在函数H(key)对任意给定的关键字值key代入函数后若能得到包含该关键字的记录在表中的地址则称表M为哈希(Hash)表函数H(key)为哈希(Hash)函数。 3.2 什么是哈希冲突(面试题) 根据一定的规则放进存放哈希值的数组中然后下标为1的数组已经有值了后面根据规则判定某个数也需要放到下标为1的数组中这样就导致了只有一个位置两个人都要坐就引起了冲突。(不同的key值产生的H(key)是一样的)。 3.3 解决哈希冲突的方法(面试题)
(1) 开放地址法 插入一个元素的时候先通过哈希函数进行判断若是发生哈希冲突就以当前地址为基准根据再寻址的方法探查序列去寻找下一个地址若发生冲突再去寻找直至找到一个为空的地址为止。所以这种方法又称为再散列法。 Hi(H(key)di)%m //开放地址法计算下标公式
Hi下标(储存的地址)
H(key)哈希函数(计算哈希值)
di增量
%取模
m哈希表的长度探查方法如下
① 线性探查 di1,2,3,…m-1冲突发生时顺序查看表中下一单元直到找出一个空单元或查遍全表。 ②二次探查 di1^2, -1^2, 2^2, -2^2 …k^2, -k^2,(km/2) 冲突发生时在表的左右进行跳跃式探测比较灵活。 ③随机探查 di伪随机数序列冲突发生时建立一个伪随机数发生器如i(ip) % mp是质数(在m范围取得质数)生成一个伪随机序列并给定一个随机数做起点每次加上伪随机数就行。 为了更好的理解我们举一个例子
设哈希表长为14哈希函数为H(key)key%11。表中现有数据15、38、61和84其余位置为空如果用二次探测再散列处理冲突则49的位置是使用线性探测法位置是解因为H(key)key%11
所以15的位置 15 % 114; 38的位置 38 % 115; 61的位置 61 % 116; 84的位置 84 % 117;(证明哈希表4,5,6,7已经有元素)因为计算下标的公式为Hi(H(key)di)mod%m
使用二次探测法
H(1) (49%11 1^1) 6;冲突
H(-1) (49%11 (-1^2)) 4;冲突 注意 -1^2 -1; (-1)^2 1;
H(2) (49%11 2^2) 9;不冲突
二次探测法49的位置就是哈希表的9。使用线性探测
H(1) (49%11 1) 6;冲突
H(2) (49%11 2) 7;冲突
H(3) (49%11 3) 8;不冲突
线性探测法49的位置就是哈希表的8。(2) 再哈希法 再哈希法又叫双哈希法有多个不同的Hash函数当发生冲突时使用第二个第三个….等哈希函数计算地址直到无冲突。虽然不易发生聚集但是增加了计算时间。 (3) 链地址法 每个哈希表节点都有一个next指针多个哈希表节点可以用next指针构成一个单向链表被分配到同一个索引上的多个节点可以用这个单向链表连接起来。 比如 66和88这两个元素哈希值都是1这就发生了哈希冲突采用链地址法可以把 66和88放在同一个链表中。如下图 (4)建立公共溢出区 将哈希表分为基本表和溢出表两部分凡是和基本表发生冲突的元素一律填入溢出表。 4. HashMap
4.1 HashMap的hash()算法(面试)
(1)为什么不是h key.hashCode()直接返回而要 h key.hashCode() ^ (h 16)来计算哈希值呢
回答减少哈希冲突 //源码计算哈希值的方法 H(key)static final int hash(Object key) {int h;return (key null) ? 0 : (h key.hashCode()) ^ (h 16);} //^ (异或运算) 相同的二进制数位上数字相同结果为0不同为1。 举例如下0 ^ 0 00 ^ 1 11 ^ 1 01 ^ 0 1// (与运算) 相同的二进制数位上都是1的时候结果为1否则为零。 举例如下0 0 00 1 01 0 01 1 1h key.hashCode() ^ (h 16)意思是先获得key的哈希值h然后 h 和 h右移十六位做异或运算运算结果再和数组长度 - 1进行与运算计算出储存下标的位置。具体原理如下
综下所述 储存下标 哈希值 数组长度 - 1//jdk1.7中计算数组下标的HashMap源码
static int indexFor(int h, int length) {//计算储存元素的数组下标return h (length-1);
}//jdk1.8中去掉了indexFor()函数改为如下
i (n - 1) hash //i就是元素存储的数组下标 某个key的哈希值为 1111 1111 1110 1111 0101 0101 0111 0101数组初始长度也是16如果没有 ^ h 16计算下标如下 1111 1111 1110 1111 0101 0101 0111 0101 //h hashcode() 0000 0000 0000 0000 0000 0000 0000 1111 //数组长度 - 1 15 (15的二进制就是 1111)------------------------------------------0000 0000 0000 0000 0000 0000 0000 0101 //key的储存下标为5由上面可知只相当于取了后面几位进行运算所以哈希冲突的可能大大增加。以上条件不变加上异或h 16之后在进行下标计算 1111 1111 1110 1111 0101 0101 0111 0101 //h hashcode()^ 0000 0000 0000 0000 1111 1111 1110 1111 //h 16------------------------------------------1111 1111 1110 1111 1010 1010 1001 1010 //h key.hashCode() ^ (h 16) 0000 0000 0000 0000 0000 0000 0000 1111 //数组长度 - 1 15 (15的二进制就是 1111)------------------------------------------0000 0000 0000 0000 0000 0000 0000 1010 //key的存储下标为10重要由上可知因为哈希值得高16位和低16位进行异或运算混合之后的哈希值低位也可能掺杂了高位的一部分特性(就是变化性增加了)这样就减少了哈希冲突。(2)为什么HashMap的初始容量和扩容都是2的次幂
回答也是为了减少哈希冲突。 原理 因为判断储存位置的下标为 i (n - 1) hashn就是数组的长度。 2的次幂 - 1其二进制都是1比如 2^4 -1 15(1111)2^5-1 31(11111)。 因为n-1和hash进行与运算只有 1 1 才为1。 因为n-1永远是2的次幂-1(n - 1) hash的结果就是 hash的低位的值。 1111 1111 1110 1111 0101 0101 0111 0101 //hash值 0000 0000 0000 0000 0000 0000 0000 1111 //数组长度 - 1 15 (15的二进制就是 1111)------------------------------------------0000 0000 0000 0000 0000 0000 0000 0101 //高位全部清零只保留末四位(就相当于保留了hash的低位)如果容量不是2次幂会怎么样呢如下图表
2次幂的时候数组长度为16n-1 16 -1 15(1111)
hash(n-1) hash储存下标01111 0000011111 0001121111 0010231111 0011341111 0100451111 01015
非2次幂的时候数组长度为10n-1 10 -1 9(1001)
hash(n-1) hash储存下标01001 0000011001 0001121001 0010031001 0011141001 0100051001 01011
重要由上看出n为2的次幂哈希冲突会更少保证元素的均匀插入。
(3)如果指定了不是2的次幂的容量会发生什么
回答会获得一个大于指定的初始值的最接近2的次幂的值作为初始容量。 比如输入 9 获得 16输入 5 获得 8。 原理如下 static final float DEFAULT_LOAD_FACTOR 0.75f; //负载因子static final int MAXIMUM_CAPACITY 1 30;//初始容量最大为 2的30次方/*** param initialCapacity 初始容量*/public HashMap(int initialCapacity) {//此处通过把第二个参数负载因子使用默认值0.75f然后调用有两个参数的构造方法this(initialCapacity, DEFAULT_LOAD_FACTOR);//调用函数一}/*** 函数一* param initialCapacity 初始容量* param loadFactor 负载因子*/public HashMap(int initialCapacity, float loadFactor) {if (initialCapacity 0) //如果初始容量小于0抛出异常throw new IllegalArgumentException(Illegal initial capacity: initialCapacity);if (initialCapacity MAXIMUM_CAPACITY) //如果初始容量超过最大容量130initialCapacity MAXIMUM_CAPACITY; //则使用最大容量作为初始容量if (loadFactor 0 || Float.isNaN(loadFactor)) //如果负载因子小于等于0或者不是数字则抛出异常throw new IllegalArgumentException(Illegal load factor: loadFactor);this.loadFactor loadFactor; //把负载因子赋值给成员变量loadFactor//调用tableSizeFor方法计算出不小于initialCapacity的最小的2的幂的结果并赋给成员变量thresholdthis.threshold tableSizeFor(initialCapacity); //调用函数二}/*** 函数二* param cap 初始容量*/static final int tableSizeFor(int cap) { //这里我们假设我们初始容量是 10//容量减1为了防止初始化容量已经是2的幂的情况在最后有n1的操作。 n 10 - 1 9int n cap - 1; //n (n | n 1) 带入得 n (1001 | 0100) 1101 n | n 1; //n (n | n 2) 带入得 n (1101 | 0011) 1111 n | n 2; //n (n | n 4) 带入得 n (1111 | 0000) 1111 n | n 4; //n (n | n 8) 带入得 n (1111 | 0000) 1111 n | n 8; //n (n | n 16) 带入得 n (1111 | 0000) 1111 15n | n 16; /**如果入参cap为小于或等于0的数那么经过cap-1之后n为负数n经过无符号右移和或操作后仍未负数,所以如果n0,则返回1;如果n大于或等于最大容量则返回最大容量;否则返回n1。n 15 1 16咱们传进来是初始容量10会自动转为16容量。**/return (n 0) ? 1 : (n MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n 1;//return (n 0) ? 1 : (n MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n 1;相当于下面这段代码if(n 0){return 1;}else{if(n MAXIMUM_CAPACITY){return MAXIMUM_CAPACITY; }else{return n 1;}}}4.2 HashMap为什么线程不安全(面试题)
(1) 多线程下扩容造成的死循环和数据丢失(jdk1.7) 在jdk1.7中链表采用的是头插法(每次插入节点都是从头插入)。 ① 假设这里有两个线程同时执行了put()操作(扩容)并进入了transfer()方法。线程A先进行操作 ② 线程A在执行到newTable[i] e后被挂起因为newTable[i] null,又因为 e.next newTable[i]所以e.next null
transfer()方法部分源码while(null !e){EntryK,V next e.next; //next 3.next 7e.next newTable[i]; //3.next nullnewTable[i] e;//线程A执行到这里被挂起了e next;}③ 开始执行线程B并完成了扩容。这时候 7.next 33.next null ④ 继续执行线程A执行newTable[i] e因为当时 e 3所以将3放到对应位置此时执行e next因为next 7(第②步)所以e 7
while(null !e){EntryK,V next e.next; //next 3.next 7e.next newTable[i]; //3.next nullnewTable[i] e;//继续从这里执行 newTable[i] 3e next; //e 7}⑤ 上轮循环之后e7从主内存中读取e.next时发现主内存中7.next3此时next3并将7采用头插法的方式放入新数组中并继续执行完此轮循环。
while(null !e){EntryK,V next e.next; //next 7.next 3e.next newTable[i]; //7.next 3newTable[i] e;//newTable[i] 7e next; //e 3}⑥上轮循环7.next3而e3执行下一次循环可以发现因为3.nextnull所以循环之后 e null所以循环会退出。
while(null !e){EntryK,V next e.next; // next 3.next nulle.next newTable[i]; //3.next 7 (此处3指向7,同时之前7也指向了3,所以会形成闭环)newTable[i] e; //newTable[i] 3e next; //e null(退出循环条件)}(2)数据覆盖(jdk1.8) jdk1.8中已经不再采用头插法改为尾插法即直接插入链表尾部因此不会出现死循环和数据丢失但是在多线程环境下仍然会有数据覆盖的问题。 当你调用put()方法时putVal()方法里面有两处代码会产生数据覆盖。 ① 假设两个线程都进行put操作线程A和线程B通过哈希函数算出的储存下标是一致的当线程A判断完之后然后挂起然后线程B判断完进入把元素放到储存位置然后线程A继续执行把元素放到储存位置因为线程A和线程B存储位置一样所以线程A会覆盖线程B的元素。 ② 同样在putVal()方法里。两个线程假设HashMap的size为15线程A从主内存获得15准备进行的操作的时候被挂起然后线程B拿到size并执行操作并写回主内存这时size是16然后线程A继续执行(这时A线程内存size还是15)操作然后写回主内存即线程A和线程B都进行了put操作然后size值增加了1所以数据被覆盖了。 4.3 HashMap解决线程不安全(面试题)
(1) 使用HashTable解决线程不安全问题(弃用) 因为HashTable解决线程不安全就是在其方法加上同步关键字(synchronized)会导致效率很低下。 (2)HashMap和HashTable的区别
①线程是否安全 HashMap线程不安全。 HashTable线程安全但是效率较低。
②是否null HashMap中key只能有一个nullvalue可以多个为null。 HashTable不允许键或值为null。
③容量 HashMap底层数组长度必须为2的幂1632128…默认为16。 HashTable底层数组长度可以为任意值导致hash算法散射不均匀容易造成hash冲突默认为11。
④底层区别 HashMap是底层由数组链表形成在JDK1.8之后链表长度大于8时转化为红黑树。 HashTable一直都是数组链表。
⑤继承关系 HashTable继承自Dictionary类。 HashMap继承自AbstractMap类。
(3)Collections.synchronizedMap(不常用)
MapString,String map Collections.synchronizedMap(new HashMap());可以看到SynchronizedMap 是一个实现了Map接口的代理类该类中对Map接口中的方法使用synchronized同步关键字来保证对Map的操作是线程安全的。 (4)ConcurrentHashMap(常用) ① jdk1.7使用分段锁底层采用数组链表的存储结构包括两个核心静态内部类 Segment(锁角色) 和 HashEntry(存放键值对)。 分段锁Segment(继承ReentrantLock来加锁)数组中一个Segment对象就是一把锁,对应n个HashEntry数组,不同HashEntry数组的读写互不干扰。 ② JDK 1.8抛弃了原有的 Segment 分段锁来保证采用Node CAS Synchronized来保证并发安全性。取消Segment类直接用数组存储键值对。 4.4 为什么使用synchronized替换ReentrantLock锁呢
① 减少内存开销。假设使用可重入锁来获得同步支持那么每个节点都需要通过继承AQS(队列同步器)来获得同步支持。但并不是每个节点都需要获得同步支持的只有链表的头节点红黑树的根节点需要同步这无疑带来了巨大内存浪费。 ② 获得JVM的支持。可重入锁毕竟是API这个级别的后续的性能优化空间很小。 synchronized则是JVM直接支持的JVM能够在运行时作出相应的优化措施锁粗化、锁消除、锁自旋等等。这就使得synchronized能够随着JDK版本的升级而不改动代码的前提下获得性能上的提升。 ③在 JDK1.6 中对 synchronized 锁的实现引入了大量的优化并且 synchronized 有多种锁状态会从无锁 - 偏向锁 - 轻量级锁 - 重量级锁一步步转换。
AQS是一个队列同步器同步队列是一个双向链表有一个状态标志位state如果state为1的时候表示有线程占用其他线程会进入同步队列等待如果有的线程需要等待一个条件会进入等待队列当满足这个条件的时候才进入同步队列ReentrantLock就是基于AQS实现的 锁升级方式就是先使用偏向锁优先同一线程然后再次获取锁如果失败就升级为CAS(compare and swap 原子操作) 轻量级锁如果失败就会短暂自旋(不停的判断比较看能否将值交换)防止线程被系统挂起。最后如果以上都失败就升级为重量级锁。 偏向锁减少无竞争且只有一个线程使用锁的情况下使用轻量级锁产生的性能消耗。轻量级锁每次申请、释放锁都至少需要一次CAS但偏向锁只有初始化时需要一次CAS。轻量级锁当有两个线程竞争的时候就会升级为轻量级锁。轻量级锁的目标是减少无实际竞争情况下使用重量级锁产生的性能消耗包括系统调用引起的内核态与用户态切换、线程阻塞造成的线程切换等。重量级锁大多数情况下在同一时间点常常有多个线程竞争同一把锁悲观锁的方式竞争失败的线程会不停的在阻塞及被唤醒态之间切换代价比较大。
4.5 HashMap底层 数组 链表 / 红黑树(面试题)
红黑树平衡二叉查找树
(1)HashMap为什么引入链表 因为HashMap在put()操作时会进行哈希值得计算算出储存下标要放在数组那个位置时当多个元素要放在同一位置时就会出现哈希冲突然后引进链表把相同位置的元素放进同一个链表(链地址法)。 (2)HashMap为什么引入红黑树 因为当链表长度大于8时链表遍历查询速度比较慢所以引入红黑树。 (3)为什么不一开始就使用红黑树 因为树相对链表维护成本更大红黑树在插入新数据之后可能会通过左旋、右旋、变色来保持平衡造成维护成本过高故链路较短时不适合用红黑树。 (4)说说你对红黑树的理解 红黑树是一种平衡二叉查找树是一种数据结构。除了具备二叉查找树特性以外还具备以下特性 1.根节点是黑色2.节点是黑色或红色3.每个叶子节点是黑色4.红色节点的子节点都是黑色5.从任意节点到其叶子节点的所有路径都包含相同数目的黑色节点 补充以上性质强制了红黑树的关键性质从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。保证了红黑树的高效。
(5) 红黑树为什么要变色、左旋和右旋操作 当我们在对红黑树进行插入和删除等操作时对树做了修改那么可能会违背红黑树的性质。 过程先变色如果变色还不满足红黑树的性质那就进行左旋或者右旋然后继续变色以此循环直至符合红黑树的性质。 4.6 HashMap链表和红黑树转换(面试题)
链表长度大于8并且表的长度大于64 数组 红黑树链表长度大于8并且表的长度不大于64 数组 链表 会扩容当数的节点小于6 数组 链表
(1) 为什么链表长度大于8并且表的长度大于64的时候链表会转换成红黑树 因为链表长度符合泊松分布长度越长哈希冲突概率就越小当链表长度为8时概率仅为 0.00000006这时是一个千万分之一的概率然后我们map也不会存储那么多的数据所以链表长度不超过8没有必要转换成红黑树。如果出现这种大量数据的话转为红黑树可以增加查询和插入效率。长度大于64只是注释写了 最低要在 4*8我也没弄懂请大佬指导。 原理如下 In usages with well-distributed user hashCodes, tree bins
are rarely used. Ideally, under random hashCodes, the
frequency of nodes in bins follows a Poisson distribution
(http://en.wikipedia.org/wiki/Poisson_distribution) with a
parameter of about 0.5 on average for the default resizing
threshold of 0.75, although with a large variance because
of resizing granularity. Ignoring variance, the expected
occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
factorial(k)). The first values are:0: 0.606530661: 0.303265332: 0.075816333: 0.012636064: 0.001579525: 0.000157956: 0.000013167: 0.000000948: 0.00000006more: less than 1 in ten million //翻译更多少于千万分之一负载因子是0.75和长度为8转为红黑树的原理由上面我们可以看出 当负载因子为0.75时哈希冲突出现的频率遵循参数为0.5的泊松分布。
常数0.5是作为参数代入泊松分布来计算的而加载因子0.75是作为一个条件。泊松分布是一种离散概率分布泊松分布的概率质量函数x(0,1,2,...)。
λ单位时间内随机事件的平均发生率。因为我们从上面知道平均发生率是0.5
e^(-0.5) 0.60653065971264 //e的负0.5次方
阶乘指从1乘以2乘以3乘以4一直乘到所要求的数。比如 3 1 * 2 * 3P(0) (0.50 * e-0.5) / 0! ≈ 0.60653066P(1) (0.51 * e-0.5) / 1! ≈ 0.30326533P(2) (0.52 * e-0.5) / 2! ≈ 0.07581633
(2) 为什么转成红黑树是8呢而重新转为链表阈值是6呢 如果转为链表也是8那如果在8这个位置发生哈希冲突那红黑树和链表就会频繁切换就会浪费资源。 (3) 为什么负载因子是0.75 根据上面的泊松分布来看表长度达到8个元素的时候概率为0.00000006几乎是一个不可能事件减少了哈希冲突。 加载因子 填入表中的元素个数 / 散列表的长度 加载因子越大填满的元素越多空间利用率越高但发生冲突的机会变大
加载因子越小填满的元素越少冲突发生的机会减小但空间浪费更多而且还会提高扩容rehash操作的次数。
“冲突的机会”与“空间利用率”之间寻找一种平衡与折中。
4.6 HashMap扩容(面试题)
(1)什么时候会发生扩容 元素个数 数组长度 * 负载因子 例如 16 * 0.75 12,当元素超过12个时就会扩容。 链表长度大于8并且表长小于64也会扩容 (2)为什么不是满了扩容 因为元素越接近数组长度哈希冲突概率就越大所以不是满了扩容。 (3)扩容过程
jdk1.7 创建一个新的table并调用transfer()方法把旧数组中的数据迁移到新数组中使用的是头插法也就是说新table中链表的顺序和旧列表中是相反的在HashMap线程不安全的情况下这种头插法可能会导致死链和数据丢失现象。jdk1.8 ①在resize()方法中定义了oldCap参数记录了原table的长度定义了newCap参数记录新table长度newCap是oldCap长度的2倍然后循环原table把原table中的每个链表中的每个元素放入新table。 ②计算索引做了优化hash原始hash oldCap原始容量 0 的元素留在原来位置 否则新位置 旧位置 oldCap原始容量。
注意
扩容是一个特别耗性能的操作所以当程序员在使用HashMap的时候估算map的大小初始化的时候给一个大致的数值避免map进行频繁的扩容。HashMap的容量达到2的30次方就不会在进行扩容了。
