HashMap工作原理
博客专区 > topwqp 的博客 > 博客详情
HashMap工作原理
topwqp 发表于2年前
HashMap工作原理
  • 发表于 2年前
  • 阅读 145
  • 收藏 14
  • 点赞 1
  • 评论 0

【腾讯云】买域名送云解析+SSL证书+建站!>>>   

摘要: HashMap工作原理

HashMap到底是如何工作的?

为什么HashMap的key必须唯一?

以下论述这两个问题:

HashMap数据结构:

{
    index,  //hashMap 位置索引
    Key,    // key 信息
    Value,  //value 信息
    Node<K,V>    //指向下一个节点
}

index 如何计算?

求对应的key的hashcode 为h 然后 :h & (length-1); 其中 length代表hashMap大小

在HashMap源码中对应的代码为:

    /**
     * Returns index for hash code h.
     */
    static int indexFor(int h, int length) {
 // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
        return h & (length-1);
    }

编程的一切理论都要实战化才有意义:直接上代码


package map;

import java.util.HashMap;
import java.util.Map;

/**
 *  hashMap  principle  Test
 * @author  SB
 *
 */
public class HashMapPrinciple {
    public static void main(String[] args) {
	     Map<String,Integer>   map = new HashMap<String,Integer>();
	     map.put("JONES", 99);
	     map.put("CLARK", 90);
	     map.put("KING", 100);
	     map.put("BLAKE", 10);
	     map.put("WARD", 99);
	     map.put("SMITH", 10);
	     map.put("FORD", 110);
	     map.put("RICK", 110);
	     map.put("SOW", 50);
	     map.put("CARL", 80);
	     map.put("WWW", 70);
	     map.put("",20);
	     map.put("",30);
	     System.out.println("map size :  " +  map.size()) ;
	     for(String  m : map.keySet()){
	    	 System.out.println(" index : " + calcIndex(calcHashValue(m)) + " ,key:" + m  +" , hashCode : " + calcHashValue(m)  );
	     }
    }
    
    public   static   int     calcHashValue(String   originInfo){
                 return  originInfo.hashCode();
    }
    
    public  static  int   calcIndex(int  hashCode){
    	return   hashCode &  15; // 15为HashMap默认长度 16-1
    }
}

输出结果为:

map size :  12
 index : 0 ,key: , hashCode : 0
 index : 8 ,key:CARL , hashCode : 2061080
 index : 15 ,key:RICK , hashCode : 2515167
 index : 7 ,key:WWW , hashCode : 86391
 index : 1 ,key:BLAKE , hashCode : 63281361
 index : 12 ,key:WARD , hashCode : 2656892
 index : 7 ,key:JONES , hashCode : 70771223
 index : 11 ,key:SOW , hashCode : 82299
 index : 1 ,key:CLARK , hashCode : 64205105
 index : 3 ,key:SMITH , hashCode : 79018979
 index : 11 ,key:FORD , hashCode : 2163899
 index : 7 ,key:KING , hashCode : 2306967

对应的存储图像直观化

输入图片说明

现在根据这个图片信息来解释开始的两个问题:

  1. HashMap采用红黑树算法(red black tree)存储这个结构

  2. 当key值相同时,对应的hashcode也一定相同,index也相同,所以put靠后的会把put之前的覆盖掉。比如本例中: index : 0 ,key: , hashCode : 0 的值为30.

3、key 值允许为空,为空时 index = 0 ,hashcode = 0

当map.get(key)时,会首先找对应的index,再匹配对应的hashcode,匹配上以后,获取对应值。

首先通过 key.hashcode() & length-1

获取 index, 再匹配 hashcode,既可以获取值。

疑问点: red black tree 如何实现?

标签: hashMap 原理
  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 0
博文 22
码字总数 11562
×
topwqp
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: