详谈HashMap和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
}

以上这篇详谈hashmap和concurrenthashmap的区别(hashmap的底层源码)就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持。