温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

ConcurrentHashMap与HashMap有哪些不同地方

发布时间:2020-12-01 17:20:41 来源:亿速云 阅读:186 作者:Leah 栏目:编程语言

本篇文章为大家展示了ConcurrentHashMap与HashMap有哪些不同地方,内容简明扼要并且容易理解,绝对能使你眼前一亮,通过这篇文章的详细介绍希望你能有所收获。

HashMap本质是数组加链表,根据key取得hash值,然后计算出数组下标,如果多个key对应到同一个下标,就用链表串起来,新插入的在前面。

ConcurrentHashMap在HashMap的基础上将数据分为多个segment,默认16个,然后每次操作对一个segment加锁,避免多线程锁的几率,提高并发效率。

1. HashMap的数据结构

HashMap底层就是一个数组结构,数组中存放的是一个Entry对象,如果产生的hash冲突,这时候该位置存储的就是一个链表了。

HashMap中Entry类的代码:

static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
final int hash;
/**
 * Creates new entry.
 */
Entry(int h, K k, V v, Entry<K,V> n) {
 value = v;
 next = n; // hash值冲突后存放在链表的下一个
 key = k;
 hash = h;
}
.........
}

HashMap其实就是一个Entry数组,Entry对象中包含了键和值,其中next也是一个Entry对象,它就是用来处理hash冲突的,形成一个链表。

2. HashMap源码分析

下面是HashMap类中的一些关键属性:

transient Entry[] table; // 存储元素的实体数组
transient int size; // 存放元素的个数
int threshold; // 临界值,当实际大小超过临界值时,会进行扩容,threshold = loadFactor * 容量
final float loadFactor; // 加载因子
transient int modCount; // 被修改的次数

如果机器内存足够,并且想要提高查询速度的话可以将加载因子设置小一点;相反如果机器内存紧张,并且对查询速度没有什么要求的话可以将加载因子设置大一点。不过一般我们都不用去设置它,让它取默认值0.75就好了。

下面是HashMap的几个构造方法:

 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);

 // Find a power of 2 >= initialCapacity
 int capacity = 1; // 初始容量
 while (capacity < initialCapacity) // 确保容量为2的n次幂,使capacity为大于initialCapacity的最小的2的n次幂
 capacity <<= 1;

 this.loadFactor = loadFactor;
 threshold = (int)(capacity * loadFactor);
 table = new Entry[capacity];
 init();
}

public HashMap(int initialCapacity) {
 this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

public HashMap() {
 this.loadFactor = DEFAULT_LOAD_FACTOR;
 threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
 table = new Entry[DEFAULT_INITIAL_CAPACITY];
 init();
}

默认初始容量为16,加载因子为0.75。上面代码中13-15行,这段代码的作用是确保容量为2的n次幂,使capacity为大于initialCapacity的最小的2的n次幂。

下面看看HashMap存储数据的过程是怎样的,首先看看HashMap的put方法:

public V put(K key, V value) {
 if (key == null) // 如果键为null的话,调用putForNullKey(value)
  return putForNullKey(value);
 int hash = hash(key.hashCode()); // 根据键的hashCode计算hash码
 int i = indexFor(hash, table.length);
 for (Entry<K,V> e = table[i]; e != null; e = e.next) { // 处理冲突的,如果hash值相同,则在该位置用链表存储
  Object k;
  if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { //如果key相同则覆盖并返回旧值
  V oldValue = e.value;
  e.value = value;
  e.recordAccess(this);
  return oldValue;
 }
 }

 modCount++;
 addEntry(hash, key, value, i);
 return null;
}

当我们往HashMap中put元素的时候,先根据key的hash值得到这个元素在数组中的位置,然后就可以把这个元素放到对应的位置中了。如果这个元素所在的位子上已经存放有其他元素了,那么在同一个位子上的元素将以链表的形式存放,新加入的放在链头,最先加入的放在链尾。从HashMap中get元素时,首先计算key的hashcode,找到数组中对应位置的某一元素,然后通过key的equals方法在对应位置的链表中找到需要的元素。

具体的实现是:当你的key为null时,会调用putForNullKey,HashMap允许key为null,这样的对象是放在table[0]中。如果不为空,则调用int hash = hash(key.hashCode());这是HashMap的一个自定义的hash方法,在key.hashCode()基础上进行二次hash,源码如下:

static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}

得到hash码之后就会通过hash码去计算出应该存储在数组中的索引,计算索引的函数如下:

static int indexFor(int h, int length) {
return h & (length-1);
}

它通过 h & (table.length-1) 来得到该对象的保存位,而HashMap底层数组的长度总是 2 的n 次方,这是HashMap在速度上的优化。当length总是 2 的n次方时,h & (length-1)运算等价于对length取模,也就是h % length,但是&比%具有更高的效率。当数组长度为2的n次幂的时候,不同的key算出的index相同的几率较小,那么数据在数组上分布就比较均匀,也就是说碰撞的几率小,相对的,查询的时候就不用遍历某个位置上的链表,这样查询效率也就较高了。

下面继续回到put方法里面,前面已经计算出索引的值了,看到第6到14行,如果数组中该索引的位置的链表已经存在key相同的对象,则将其覆盖掉并返回原先的值。如果没有与key相同的键,则调用addEntry方法创建一个Entry对象,addEntry方法如下:

void addEntry(int hash, K key, V value, int bucketIndex) {
 Entry<K,V> e = table[bucketIndex]; // 如果要加入的位置有值,将该位置原先的值设置为新entry的next,也就是新entry链表的下一个节点
 table[bucketIndex] = new Entry<>(hash, key, value, e);
 if (size++ >= threshold) // 如果大于临界值就扩容
 resize(2 * table.length); // 以2的倍数扩容
}

参数bucketIndex就是indexFor函数计算出来的索引值,第2行代码是取得数组中索引为bucketIndex的Entry对象,第3行就是用hash、key、value构建一个新的Entry对象放到索引为bucketIndex的位置,并且将该位置原先的对象设置为新对象的next构成链表。第4行和第5行就是判断put后size是否达到了临界值threshold,如果达到了临界值就要进行扩容,HashMap扩容是扩为原来的两倍。resize()方法如下:

void resize(int newCapacity) {
 Entry[] oldTable = table;
 int oldCapacity = oldTable.length;
 if (oldCapacity == MAXIMUM_CAPACITY) {
  threshold = Integer.MAX_VALUE;
  return;
 }
8
 Entry[] newTable = new Entry[newCapacity];
 transfer(newTable); // 用来将原先table的元素全部移到newTable里面
 table = newTable; // 再将newTable赋值给table
 threshold = (int)(newCapacity * loadFactor); // 重新计算临界值
}

扩容是需要进行数组复制的,上面代码中第10行为复制数组,复制数组是非常消耗性能的操作,所以如果我们已经预知HashMap中元素的个数,那么预设元素的个数能够有效的提高HashMap的性能。下面是get方法的源码:

public V get(Object key) { 
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
// 找到数组的下标,进行遍历
for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
 return e.value; // 找到则返回
}
return null; // 否则,返回null
}

上述内容就是ConcurrentHashMap与HashMap有哪些不同地方,你们学到知识或技能了吗?如果还想学到更多技能或者丰富自己的知识储备,欢迎关注亿速云行业资讯频道。

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI