HashMap的存储结构及原理

HashMap的存储结构及原理

大家好,又见面了,我是全栈君。

1、HashMap的数据结构(HashMap通过hashcode对其内容进行高速查找,是无序的)


  数据结构中有数组和链表来实现对数据的存储,但这两者基本上是两个极端。

  数组 :数组的存储区是连续的,占用内存严重,故空间复杂度非常大。但数组的二分查找时间度小;数组的特点:寻址easy,插入和

删除困难。

  链表 :链表的储存区离散。占用内存比較宽松。故空间复杂度非常小,但时间复杂度大;链表的特点:寻址困难,插入和删除easy。

哈希表

  HashMap是由数组+链表组成。寻址easy,插入和删除easy。(存储单元数组Entry[],数组里面包括链表

  HashMap事实上也是由一个线性的数组实现的。

所以能够理解为其存储数据的容器就是一个线性容器;

  HashMap里面有一个内部静态类Entry,其重要的属性有key,value,next,从属性key,value 就能够非常明显的看出来 Entry就是

  HashMap键值对实现的一个基础bean;也就是说HashMap的基础就是一个线性数组,这个数组就是Entry[]。Map里面的内容都保存

在Entry[]中;

    /**
     * The table, resized as necessary. Length MUST Always be a power of two.
     */

    transient Entry[] table;

2、HashMap的存取实现


2.1:存储

这里HashMap用了一个算法。

//存储时候:

int hash=key.hashCode(); //获取key的hashCode,这个值是一个固定的int值

int index=hash%Entry[].length。//获取数组下标:key的hash值对Entry数组长度进行取余

Entry[index]=value。

注意:假设两个key通过hash%Entry[].length得到的index同样。会不会覆盖?

是不会的。Entry类有一个next属性,作用是指向下一个Entry。打个例如, 第一个键值对A进来。通过计算其key的hash得到的

index=0。记做:Entry[0] = A。一会后又进来一个键值对B,通过计算其index也等于0,如今怎么办?HashMap会这样做:B.next =

 A,Entry[0] = B,假设又进来C,index也等于0,那么C.next = B,Entry[0] = C;这样我们发现index=0的地方事实上存取了A,B,C三个键值对,他

们通过next这个属性链接在一起。

所以疑问不用操心。

也就是说Entry[]数组中存储的是最后插入的数据


	 public V put(K key, V value) {
	        if (key == null)
	            return putForNullKey(value); //null总是放在数组的第一个链表中
	        int hash = hash(key.hashCode());
	        int i = indexFor(hash, table.length);
	        //遍历链表
	        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
	            Object k;
	            //假设key在链表中已存在,则替换为新value
	            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
	                V oldValue = e.value;
	                e.value = value;
	                e.recordAccess(this);
	                return oldValue;
	            }
	        }
	        modCount++;
	        addEntry(hash, key, value, i);
	        return null;
	    }

	 
	void addEntry(int hash, K key, V value, int bucketIndex) {
	    Entry<K,V> e = table[bucketIndex];
	    table[bucketIndex] = new Entry<K,V>(hash, key, value, e); //參数e, 是Entry.next
	    //假设size超过threshold,则扩充table大小。再散列
	    if (size++ >= threshold)
	            resize(2 * table.length);
	}

2.2:取值

    获取key的hashcode指,通过hash值去hash%Entry[].length  获取Entry[hash%Entry[].length],定位到该数组元素之后,再遍历该元

素处的链表。

//取值时候:

int hash=key.hashCode();

int index =hash%Entry[].length;

return Entry[index];


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

      当哈希表的容量超过默认容量时,必需要调整table的大小。

当容量达到最大值时,该方法Integer.MAX_VALUE返回。这时。就需要创建

一张表,将原来的表映射到新表中。


3、HashMap、HashTable和ConcurrentHashMap的线程安全问题

HashMap:线程不安全的。

HashTable:锁住整张hash表,让线程独占。hashMap同意为空。

通过分析Hashtable就知道,synchronized是针对整张Hash表的,每次锁住整张表

让线程独占。安全的背后是巨大的浪费。

ConcurrentHashMap:一个更快的hashmap,它提供了好得多的并发性。多个读操作差点儿总能够并发地运行。

他是锁段(默认:把hash表分为16个

,在get,put,remove等操作中,ConcurrentHashMap仅仅锁定当前须要用到的段,仅仅有在求size的时候才锁定整张hash表。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115749.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号