文档章节

HashMap工作原理

topwqp
 topwqp
发布于 2016/01/28 11:17
字数 511
阅读 148
收藏 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之间的区别,那么为何这道面试题如此特殊呢?是因为这道题考...

半夏alvin
2016/01/07
21
0
HashMap 工作原理

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

The_flying_pig
2017/09/19
0
0
HashMap的工作原理及HashMap和Hashtable的区别

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

袁梓皓
2016/03/09
91
0

没有更多内容

加载失败,请刷新页面

加载更多

Redis常用命令

keys 我把这个命令放在第一位,是因为笔者曾经做过的项目,以及一些朋友的项目,都因为使用keys这个命令,导致出现性能毛刺。这个命令的时间复杂度是O(N),而且redis又是单线程执行,在执行k...

谢思华
26分钟前
2
0
关于css宽度分离

所谓宽度分离就是width 属性不与影响宽度的 padding/border(有时候包括 margin)属性共存 例如: .box{width:200px;padding:20px;border:1px solid;} 为何要做宽度分离 一说到分离就是为了好...

莫西摩西
37分钟前
1
0
Linux常用命令

###############常用命令说明############################## cat /proc/version 显示内核的版本 mv dir1 new_dir 重命名/移动 一个目录 rm -rf a.txt b.txt c.txt 删除多个文件 chmod 777 ......

lyle_luo
43分钟前
2
0
全国地区代码科普

全国地区代码表 天津市 地区代码 地区名称 1100 天津市 辽宁省 地区代码 地区名称 2210 沈阳市 2210 法库县 2210 康平县 2210 辽中县 2210 新民市 2220 大连市 2222 普兰店市 2223 庄河市 22...

恋码之子
44分钟前
1
0
DbForge Schema Compare for MySQL入门教程:生成比较报告

【dbForge Schema Compare for MySQL下载】 当架构比较完成后,您可以生成比较报告以保留架构更改的记录。 1. 在“Comparison” 菜单中,单击“Generate Comparison Report” 。将打开“Gen...

Miss_Hello_World
45分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部