文档章节

HashMap工作原理

topwqp
 topwqp
发布于 2016/01/28 11:17
字数 511
阅读 152
收藏 14

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 如何实现?

© 著作权归作者所有

共有 人打赏支持
topwqp
粉丝 0
博文 22
码字总数 11562
作品 0
西城
私信 提问
HashMap 核心源码分析 (jdk8)

写在前面 如果对 HashMap 的基本工作原理不清楚,继续阅读后续内容的效果不是很好,建议先学习前置知识HashMap 基本工作原理 : https://my.oschina.net/j4love/blog/1797058 java.util.Has...

j4love
05/04
0
0
常见面试题——HashMap工作原理的介绍!

HashMap的工作原理是近年来常见的Java面试题。几乎每个Java程序员都知道HashMap,都知道哪里要用HashMap,知道HashTable和HashMap之间的区别,那么为何这道面试题如此特殊呢?是因为这道题考...

欧阳海阳
06/24
0
0
HashMap 工作原理

HashMap的工作原理是近年来常见的Java面试题。几乎每个Java程序员都知道HashMap,都知道哪里要用HashMap,知道Hashtable和HashMap之间的区别,那么为何这道面试题如此特殊呢?是因为这道题考...

The_flying_pig
2017/09/19
0
0
HashMap的工作原理【文字版】

HashMap的工作原理是近年来常见的Java面试题。几乎每个Java程序员都知道HashMap,都知道哪里要用HashMap,知道Hashtable和HashMap之间的区别,那么为何这道面试题如此特殊呢?是因为这道题考...

半夏alvin
2016/01/07
21
0
HashMap的工作原理及HashMap和Hashtable的区别

HashMap的工作原理是近年来常见的Java面试题。几乎每个Java程序员都知道HashMap,都知道哪里要用HashMap,知道Hashtable和HashMap之间的区别,那么为何这道面试题如此特殊呢?是因为这道题考...

袁梓皓
2016/03/09
91
0

没有更多内容

加载失败,请刷新页面

加载更多

什么是以太坊DAO?(二)

Decentralized Autonomous Organization,简称DAO,以太坊中重要的概念。一般翻译为去中心化的自治组织。 在上一节中,我们为了展示什么是DAO创建了一个合约,就像一个采用邀请制的俱乐部,会...

geek12345
29分钟前
4
0
全屋WiFi彻底无死角 这才是终极解决方案

无线网络现在不仅在家庭中不可或缺,在酒店、医院、学校等场景中的需求也越来越多。尤其是这些场景中,房间多但也需要每个房间都能够完美覆盖WiFi,传统的吸顶式AP就无法很好的解决问题。 H3...

linux-tao
42分钟前
4
0
Python日期字符串比较

需要用python的脚本来快速检测一个文件内的二个时间日期字符串的大小,其实实现很简单,首先一些基础的日期格式化知识如下 复制代码 %a星期的简写。如 星期三为Web %A星期的全写。如 星期三为...

dragon_tech
43分钟前
3
0
ORA 各种oraclesql错误

ORA-00001: 违反唯一约束条件 (.) ORA-00017: 请求会话以设置跟踪事件 ORA-00018: 超出最大会话数 ORA-00019: 超出最大会话许可数 ORA-00020: 超出最大进程数 () ORA-00021: 会话附属于其它某...

青峰Jun19er
47分钟前
3
0
没错,老板让我写个 BUG!

前言 标题没有看错,真的是让我写个 bug! 刚接到这个需求时我内心没有丝毫波澜,甚至还有点激动。这可是我特长啊;终于可以光明正大的写 bug 了🙄。 先来看看具体是要干啥吧,其实主要就是...

crossoverJie
今天
135
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部