文档章节

HashMap工作原理

topwqp
 topwqp
发布于 2016/01/28 11:17
字数 511
阅读 147
收藏 14
点赞 1
评论 0

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
集合——HashMap的工作原理

http://www.importnew.com/16301.html 好的链接 HashMap的工作原理? 1.HashMap的底层结构是数组加链表; a.HashMap包含一个Entry(key,value,next,hash)的内部类,key/value放入HashMap的时候...

亚特兰缇斯
2015/03/03
0
0
HashMap和HashSet的区别

HashMap和HashSet的区别是Java面试中最常被问到的问题。如果没有涉及到Collection框架以及多线程的面试,可以说是不完整。而Collection框架的问题不涉及到HashSet和HashMap,也可以说是不完整...

LCZ777
2014/03/29
0
0
为什么要学习HashMap的底层原理?

本文转载自公众号 码农翻身 上周发了一篇文章《漫画:什么是HashMap?》,引起了不少人的讨论,有一个人的留言引发了我的思考:“作为一个程序员, 真的有必要学习这些底层原理吗? 我会用了...

bjweimengshu
2017/12/03
0
0
HashMap和TreeMap

hashMap HashMap工作原理我对hashMap的认识基本是对的,hashCode() and equals() is important for hashMap. 除了这个完全不知道 当重新调整HashMap大小的时候,确实存在条件竞争,因为如果两...

Finley.Hamilton
2014/12/04
0
0
Java常见面试题及答案 21-30(集合类)

21.HashMap的工作原理是什么? HashMap内部是通过一个数组实现的,只是这个数组比较特殊,数组里存储的元素是一个Entry实体(jdk 8为Node),这个Entry实体主要包含key、value以及一个指向自身的...

t4i2b10x4c22nf6a
2017/12/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

什么是Base64

一、什么是Base64? 百度百科中对Base64有一个很好的解释:“Base64是网络上最常见的用于传输8Bit字节码的编码方式之一,Base64就是一种基于64个可打印字符来表示二进制数据的方法”。 什么是...

Jack088
6分钟前
0
0
SQL多表联查leftjoin左边加表单

SELECT IFNULL(u.USER_ACCOUNT, o.USER_ACCOUNT) u.USER_ACCOUNT, o.* FROM gh_orders o LEFT JOIN gh_user u ON o.PARENT_ID = u.ROW_ID 1.假如u.USER_ACCOUNT不空返回u.USER_ACCOUNT,否则返......

森火
10分钟前
0
0
expect脚本同步文件、expect脚本指定host和要同步的文件、构建文件分发系统

expect脚本同步文件 更改权限 执行脚本 查看执行结果 expect eof需要加上,作用是等脚本命令执行完再进行退出 expect脚本指定host和要同步的文件 更改权限,执行脚本 构建文件分发系统 需求背...

Zhouliang6
48分钟前
1
0
Hive应用:外部分区表

Hive应用:外部分区表 介绍 Hive可以创建外部分区表。创建表的时候,分区要在建表语句中体现。建完之后,你不会在表中看到数据,需要进行分区添加,使用alter语句进行添加。然后数据才会显示...

星汉
58分钟前
3
0
点击Enter登录

1. 效果 2. 实现过程(记得引入jq文件) //6.回车事件 登录 $(function() { document.onkeydown = function(event) { var e = event || window.event || arguments.callee.caller.arguments......

Lucky_Me
今天
1
0
点击菜单内容切换

<!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>Title</title> <style> .menu{ height: 38px; background-color: #eeeeee; line-height: 38px; } .mao{ ......

南桥北木
今天
1
0
OSChina 周六乱弹 —— 妹子和游戏哪个更好玩

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @andonny :分享唐朝乐队的单曲《国际歌》 《国际歌》- 唐朝乐队 手机党少年们想听歌,请使劲儿戳(这里) @举个栗子- :日常祈雨 邪恶的大祭...

小小编辑
今天
613
8
流利阅读笔记32-20180721待学习

“人工智能”造假:只有人工,没有智能 Lala 2018-07-21 1.今日导读 当今社会,擅长单个方面的人工智能已经盛行,手机借助 AI 智慧防抖技术帮助大家拍出清晰照片,谷歌研发的 AI 助手将可以帮...

aibinxiao
今天
10
0
我的成长记录(一)

今天突然精神抖擞,在我的博客下新开一项分类>成长记录,专门记录每隔一段时间我的一点感悟吧。因为今天才专门花时间新开这样一个分类,所以以前有过的一些感悟没有记录下来,现在已经想不起...

dtqq
今天
1
0
机器学习管理平台 MLFlow

最近工作很忙,博客一直都没有更新。抽时间给大家介绍一下Databrick开源的机器学习管理平台-MLFlow。 谈起Databrick,相信即使是不熟悉机器学习和大数据的工程湿们也都有所了解,它由Spark的...

naughty
今天
19
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部