HashMap源码分析,看这篇文章就够了

muchlab 2019-09-23

HashMap源码分析,看这篇文章就够了

HashMap简介

HashMap是开发中使用频率最高的用于映射(键值对 key value)处理的数据结构,我们经常把hashMap数据结构叫做散列链表;

ObjectI entry<Key,Value>,entry<Key,Value>] 可以将数据通过键值对形式存起来

特点

  • HashMap根据键的hashcode值存储数据,大多数情况可以直接定位到它的值,因而具有很快的访问速度,但遍历顺序是不确定的

想要使得遍历的顺序就是插入的顺序,可以使用LinkedHashMap,LinkedHashMap是HashMap的一个子类,保存了记录的插入顺序,在用Iterator遍历LinkedHashMap时,先得到的记录肯定是先插入的,也可以在构造时带参数,按照访问次序排序。

public class HashMapTest {
 public static void main(String[] args) {
 HashMap hashMap = new HashMap();
 hashMap.put(2,"bbb");
 hashMap.put(3,"ccc");
 hashMap.put(1,"aaa");
 System.out.println("HashMap的遍历顺序:"+hashMap);
 LinkedHashMap linkedHashMap = new LinkedHashMap();
 linkedHashMap.put(2,"bbb");
 linkedHashMap.put(3,"ccc");
 linkedHashMap.put(1,"aaa");
 System.out.println("LinkedHashMap的遍历顺序:"+linkedHashMap);
 }
}
HashMap的遍历顺序:{1=aaa, 2=bbb, 3=ccc}
LinkedHashMap的遍历顺序:{2=bbb, 3=ccc, 1=aaa}

线程不安全的HashMap

因为多线程环境下,使用Hashmap进行put操作会引起死循环,导致CPU利用率接近100%,所以在并发情况下不能使用HashMap。

  • HashMap最多只允许一条记录的键为null,允许多条记录的值为null
  • HashMap非线程安全,如果需要满足线程安全,可以一个Collections的synchronizedMap方法使HashMap具有线程安全能力,或者使用 ConcurrentHashMap

效率低下的HashTable容器

HashTable容器使用synchronized来保证线程安全,但在线程竞争激烈的情况下HashTable的效率非常低下。因为当一个线程访问HashTable的同步方法时,其他线程访问HashTable的同步方法时,可能会进入阻塞或轮询状态。如线程1使用put进行添加元素,线程2不但不能使用put方法添加元素,并且也不能使用get方法来获取元素,所以竞争越激烈效率越低。

ConcurrentHashMap的锁分段技术

HashTable容器在竞争激烈的并发环境下表现出效率低下的原因,是因为所有访问HashTable的线程都必须竞争同一把锁,那假如容器里有多把锁,每一把锁用于锁容器其中一部分数据,那么当多线程访问容器里不同数据段的数据时,线程间就不会存在锁竞争,从而可以有效的提高并发访问效率,这就是ConcurrentHashMap所使用的锁分段技术,首先将数据分成一段一段的存储,然后给每一段数据配一把锁,当一个线程占用锁访问其中一个段数据的时候,其他段的数据也能被其他线程访问。

通常会见到数据库优化,具体就是索引优化,那什么是索引优化呢?

举个例子,微信通讯录,最右侧会有a-z的排序,这就是索引,把数据分组,用到了hashMap数据结构

为什么键一个set集合,值是一个value集合

public abstract class AbstractMap<K,V>implements Map<K,V>{
Set<K>keyset;
Collection<V>valuescollection;
set数据结构:元素不能相同
collection数据结构:元素可以相同
因为在hashMap中,key(键)不能相同,value(值)是可以相同的

HashMap源码分析

核心成员变量

transient HashMapEntry<k, V>[] table;         //键值对的数组,存着每一个键值对
transient HashMapEntry<K,V>entryForNullKey;     //没有键的键值对
private transient Set<Map.Entry<K, V>> entrySet; //HashMap将数据转换成set的另一种存储形式,这个变量主要用于迭代功能。
transient int size;            //HashMap中实际存在的Node数量,注意这个数量不等于table的长度,甚至可能大于它,因为在table的每个节点上是一个链表(或RBT)结构,可能不止有一个Node元素存在。
transient int modCount;          //HashMap的数据被修改的次数,这个变量用于迭代过程中的Fail-Fast机制,其存在的意义在于保证发生了线程安全问题时,能及时的发现(操作前备份的count和当前modCount不相等)并抛出异常终止操作。
private transient int threshold;    //HashMap的扩容阈值,在HashMap中存储的键值对超过这个数量时,自动扩容容量为原来的二倍。
final float loadFactor;         //HashMap的负载因子,可计算出当前table长度下的扩容阈值:threshold = loadFactor * table.length。

hashMap常量

private static final int MINIMUM_cAPACITY = 4; //最小容量
private static final int MAXIAMM_CAPACITY = 1<<30; //最大容量,即2的30次方 (左移乘2,右移除2)
static final float DEFAULT_LOAD_FACTOR = 0.75f; //加载因子,用于扩容,容量达到三分之二时,就准备扩容了
static final int MIN_TREEIFY_CAPACITY = 64;//默认的最小的扩容量64,为避免重新扩容冲突,至少为4 * TREEIFY_THRESHOLD=32,即默认初始容量的2倍
private static final Entry[] EMPTY_TABLE = new HashMapEntry[MINIMUM CARACITY >>>1];//键值对数组最小容量(空的时候)

构造方法

  //空参构造,使用默认的加载因子0.75
  public HashMap() {
 this.loadFactor = DEFAULT_LOAD_FACTOR; 
 }

   //设置初始容量,并使用默认的加载因子
 public HashMap(int initialCapacity) {
 this(initialCapacity, DEFAULT_LOAD_FACTOR);
 }

 //设置初始容量和加载因子,
 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 interface Map<K,V>{}
public static interface Entry<k,V){}
public boolean equals(Object object); //要重写,因为要相等的话,键和值都要相同
public K getkey();       //获取键
public V getValue();      //获取值
public V setValue(V object); //设置值
public void clear();      //清除这个map
public boolean containskey(Object key); //是否包含某个键
public boolean containsValue(Object value); //是否包含某个值
public Seft<Map. Entry<K,V>>entryset(); //获取实体集合
public Set<k>keyset();     //获取键的集合
public Set<k>Valueset();    //获取值的集合
public V put(K key,V vale); //往里面添加一个键值对
public void putAll(Map<? extends K,?extends V>map); //添加一个键值对的、小的map
public V remove(Object key); //通过一个键移除一个值
public int size();        //键值对的数量
public Collectign<V>values(); //值的集合

什么是HASH

是根据文件的内容的数据 通过逻辑运算得到的数值, 不同的文件(即使是相同的文件名)得到的HASH值是不同的, 所以HASH值就成了每一个文件在EMULE里的身份证.

secondary : 第二的
table:存储键值对的数组
tab.lenth=下标最大值
e:tab[index] : 一维数组第一个元素,整个链表的头结点

put方法

下 1 代表下一个代码块有此方法 下下 2 代表下下一个代码块有此方法 依次类推

@Override
public V put(k key, V value) {
 if (key == null) {
 return putValueForNu1lKey(value);         //放一个空key的值 注:hashMap的值是可以为空的
  }
 int hash = Collections.下下2secondaryHash(key); //首先拿到键的hash值,这个key传进来之后进行两次hash:先拿到下 key.hashCode()本身hash值,再把它作为参数(object key)传进来,就是二次hash
                                                       目的:为了不能key一直在一个数据域里,要分散一些,均匀排列,在0-9
 下下下1HashMapEntry<K, V>[] tab = table;     //为了安全问题声明局部变量tab
 int index = hash & (tab.length - 1);      //通过计算hash值再进行一个与运算,获取下标要放在哪个地方。 就相当于微信索引,计算出所在位置,
                                打个比方,成--c,放在c区域里 一个区域可以有多个键只需要两行代码,就能找到key(n)所在的散列,
                                比如有10个链表,之前需要查10次,现在只需要查10分之1次,效率提高10倍,再通过迭代找具体元素,100个链表效率就提高100倍
 for (HashMapEntry<K, V> e = tab[index]; e! = null; e = e.next) { //遍历整个下标下面整个链表,e:头结点 ,如果头结点不等于空,就让头结点等于他的下一个结点
     
if (e.hash == hash && key.equals(e.key)) {   //键值对里的hash等于算出来的hash ,然后发现放进来的这个key和链表里的这个key相同,就覆盖
 preModify(e);覆盖
 V oldValue = e.value;       //以前的值oldValue赋值给新的value
 e.value = value;
 return oldValue;
 }
 }
      modCount++;          //找不到计数+1      
      if(size++ > threshold){ //数量有大小,也就是size,如果size++大于容量因子极限,就扩充
        tab = doubleCapacity(); //容量乘以2,扩大两倍。最小是4,22 23 24 25 26 . . .
        index = hash &(tab.1ength-1); //扩完容再重新计算一遍下标的值
      }        
      addNewEntry(key, value, hash, index); 
      return nul1;
 }
public static int ①secondaryHash(Object key){
  return ②secondaryHash(key. hashCode()); //先获取key本身的hashcode,再经过一次hash,调用secondaryHash
}
private static int 上上2secondaryHash(int h) {
 h += (h << 15) ^ 0xffffcd7d;
 h ^= (h >>> 10);
 h += (h << 3);
 h ^= (h >>> 6);
 h += (h << 2) + (h << 14);
 return h ^ (h >>> 16);
}

hashMap不仅仅是一种单纯的一维数组,有键key,有值value,还有next指针,这样的好处是 HashMap根据键的hashcode值存储数据,大多数情况可以直接定位到它的值,因而具有很快的访问速度,但遍历顺序是不确定的

static class 上上上1HashMapEntry<K, V> implements Entry<K, V> {

final K key;

V value;

final int hash;

HashMapEntry<K, V> next; //如果出现相同的键,就通过这个指针指向下一个

HashMapEntry(K key, V value, int hash, HashMapEntry<K, V> next) {

this.key = key;

this.value = value;

this.hash = hash;

this.next = next;

}

oldCapacity:扩容之前的长度

newTable:

private HashMapEntry<K,V>[] doubleCapacity(){

HashMapEntry<K,V>[] oldTable=table;   //作为局部变量赋值

int oldCapacity =oldTable.1engtth;

if(oldCapacity == MAXTMUM_CAPACITY){ //现在的长度就等于最大就不扩容了

  return oldTable;

}

int newCapacity = oldCapacity*2;     //否则,扩容2倍

HashMapEntry<K,V>[] newTable = makeTable(newCapacity); //声明了一个newTable,让他的长度等于newCapacity

if(size==0){                 //没元素在里面

  return newTable;

}

  for(int j=Q;j<b1dcapacity;j++){     //遍历,为了把老数组里的元素放到新数组里面来

   HashMapEntry<K,V>e=oldTable[j];   //拿到老的数组里的每一个键值对

   if(e==nul1){

     continue;

   }  //键值对为空,则不管

  int highBit=e. hash & oldCapacity; //拿到键值对里的hash和oldCapacity长度,进行取小(highBit)

  HashMapEntry<K,V>broken=null;

  newTable[j | highBit]=e;    //把highBit放在newTable里面,和j进行一个或运算,其实就是把元素丢到新的里面来

  for(HashMapEntry<K,V>n=e. next;n!=null;e=n,n=n. next){ //把串里的数据全部拿出来,重新计算下标

    int nextHighBit=n. hash & oldCapacity;

    if(nextHighBit!=highBit){      //如果后面子串和前面这个串,计算出来的下标不同,不能再放在这个数组(相当于微信的一个索引)里了

      if(broken==null)         //不相等

        newTable[j | nextHighBit]=n; //应该放在newTable新的下标去 或运算的时候分成两个区间

      else

        broken.next = n;         //如果相等,放在next后面,继续串起来

        

      broken=e;

      heigBit = nextHighBit;

    }

  }

  if(broken !=null)

    broken. next=null;

    }

  return newTable;

}

table[index] = next 也就是链表中下一个元素

table[index]就相当于微信同一个索引下的某个元素,有两个了,再添加,就用next指向下一个元素

串只需要用头结点来表示,要做到是先把新结点连接到串里面来,然后再让tab[index]等于这个串,这个串本身就是这个头结点,比如现在有三个串(头结点也有一个),新进来的串放在前面

void addNewEntry(K key,V value,int hash,int index){

table[index]=new HashMapEntry<K,V>(key,value,hash,table[index](next指针)); 蓝色为新结点,放在tab[index]里面来,就是头结点,相当于新结点变成了头结点,

                                           而新结点作为头结点的next指针,作为一个引用引进来了

,这个图就是,tab[index]这个一维数组中的某个元素或存储区域,让它等于新加进来的元素--newHashMap,让新进来的元素的next指针指向tab[index]

remove

tab[index]:头结点

prev=null 默认为空

@override
public V remove(object key) {
  if (key == null) {
    return removeNullke(); //移除空键但有值的键值对
  }
 int hash = Collections.secondaryHash(key); 
  HashMapEntry<K, V>[] tab = table; 
  int index = hash & (tab.length - 1); 
  for (HashMapEntry<K, V> e = tab[index], prev = null; //遍历串里的每一个元素,让头结点等于e
      e != null;prev = e, e = e.next){ //让头结点e等于prev,又让e.next(头结点的下一个元素等于e)
         二次遍历
    if (e.hash == hash && key.equals(e.key)) { hash相等,又能equals,说明找到了这个结点
      if (prev == null) {
        tab[index] = e.next; 让头结点不再等于之前的prev,把e放在头结点位置,然后e.next就是tab[index](头结点),成功上位了哈哈
      } else {
        prev.next = e.next; prev.next不指向下一个元素了,指向下一个的下一个(e.next),就表示把e删除了
      modCount++;
      size++;

要删除一个key1,找到下标索引就是index=0 第一列,但是这个index=0有很多键值对,不能直接把index=0里的所有键值对删除吧,所以要先查找找出来,删除需要的键值对

修改元素:

元素的修改也是put方法,因为key是唯一的,所以修改元素,是把新值覆盖旧值。

HashMap源码分析,看这篇文章就够了

第一排,只有最后4位才有效,因为与运算全是1才为1,所以 0000=1001=0(最小值) 1001+1001=9(最大值)

hash%10也是(0~9),因为hash不固定

与运算lenth-1均匀的分布成0~9 或运算分成两个区间

hash相同 key不一定相同>> key1 key2产生的hash很有可能是相同的,如果key真的相同,就不会存在散列链表了,散列链表是很多不同的键算出的hash值和index相同的

key相同 经过两次hash hash一定相同

tips

想理解数据结构源码,得理清楚当一个新的元素被添加进来以后,会和之前的老的元素产生什么关系

首先看继承的关系,看成员变量,看元素之间的关系,看元素之间的关系就是在添加元素的时候,这组元素和之前的元素有什么关系,put方法

关注作者:JAVA高级程序员

专注分享:(高可用、高并发、高性能及分布式、Jvm性能调优、Spring源码,MyBatis,Netty,Redis,Kafka,Mysql,Zookeeper,Tomcat,Docker,Dubbo,Nginx等技术...)

欢迎转发,评论~~~

每天Java一下,成为架构师!

相关推荐