浅谈hashmap的底层原理
关键词：
本文整理自漫画：什么是HashMap? -小灰的文章 。已获得作者授权。
HashMap 是一个用于存储Key-Value 键值对的集合，每一个键值对也叫做Entry。这些个Entry 分散存储在一个数组当中，这个数组就是HashMap 的主干。
HashMap 数组每一个元素的初始值都是Null。
1. Put 方法的原理
调用Put方法的时候发生了什么呢？
比如调用 hashMap.put("apple", 0) ，插入一个Key为“apple"的元素。这时候我们需要利用一个哈希函数来确定Entry的插入位置（index）：
index = Hash（"apple"）
假定最后计算出的index是2，那么结果如下：
但是，因为HashMap的长度是有限的，当插入的Entry越来越多时，再完美的Hash函数也难免会出现index冲突的情况。比如下面这样：
这时候该怎么办呢？我们可以利用链表来解决。
HashMap数组的每一个元素不止是一个Entry对象，也是一个链表的头节点。每一个Entry对象通过Next指针指向它的下一个Entry节点。当新来的Entry映射到冲突的数组位置时，只需要插入到对应的链表即可：
新来的Entry节点插入链表时，使用的是“头插法。
2. Get方法的原理
使用Get方法根据Key来查找Value的时候，发生了什么呢？
首先会把输入的Key做一次Hash映射，得到对应的index：
index = Hash（“apple”）
由于刚才所说的Hash冲突，同一个位置有可能匹配到多个Entry，这时候就需要顺着对应链表的头节点，一个一个向下来查找。假设我们要查找的Key是“apple”：
第一步，我们查看的是头节点Entry6，Entry6的Key是banana，显然不是我们要找的结果。
第二步，我们查看的是Next节点Entry1，Entry1的Key是apple，正是我们要找的结果。
之所以把Entry6放在头节点，是因为HashMap的发明者认为，后插入的Entry被查找的可能性更大。
3. HashMap的初始长度
初始长度为16，且每次自动扩容或者手动初始化的时候必须是2的幂。
如何进行位运算呢？有如下的公式（Length是HashMap的长度）：
之前说过，从Key映射到HashMap数组的对应位置，会用到一个Hash函数：
index = Hash（“apple”）
如何实现一个尽量均匀分布的Hash函数呢？我们通过利用Key的HashCode值来做某种运算。
index = HashCode（Key） & （Length - 1）
下面我们以值为“book”的Key来演示整个过程：
- 计算book的hashcode，结果为十进制的3029737，二进制的
101110001110101110 1001。
- 假定HashMap长度是默认的16，计算Length-1的结果为十进制的15，二进制的1111。
- 把以上两个结果做与运算，
101110001110101110 1001 & 1111 = 1001，十进制是9，所以 index=9。
可以说，Hash算法最终得到的index结果，完全取决于Key的Hashcode值的最后几位。这里的位运算其实是一种快速取模算法。
HashMap 的size为什么必须是2的幂?。这是因为2的幂用二进制表示时所有位都为1，例如16-1=15 的二进制就是1111B。我们说了Hash算法是为了让hash 的分布变得均匀。其实我们可以把1111看成四个通道，表示跟1111 做&运算后分布是均匀的。假如默认长度取10，二进制表示为1010，这样就相当于有两个通道是关闭的，所以计算出来的索引重复的几率比较大。
想看原作者的文章可以看看这个公众号。
浅谈hashmap实现原理
我们都知道数组和链表的优劣，那HashMap有效地整合了数组和链表，形成了新的一种数据装载模型。 利用数组+链表的优势1、减少数组不必要空间的开辟（假如单纯利用数组实现装载，我们总要考虑预先分配一部分内存，总不... 查看详情
浅谈java集合（底层源码解析）
...种经常用的Map、List、Set。1、Map一、背景二、Map家族三、HashMap、Hashtable等四、HashMap底层数据结构2、List一、List 包括的子类二、ArrayList三、ArrayList 源码分析四、LinkedList五、Linked 查看详情
hashmap的底层原理
HashMap HashMap是基于哈希表的Map接口的非同步实现，Java最基本数据结构就是两种，一种是数组，一种是引用。所有的数据结构都可以用这两个基本结构来构造的，HashMap也不例外。HashMap实际上是一个“链表散列”... 查看详情
浅谈arraylist的底层扩容的原理(代码片段)
ArrayList扩容机制的源码详解一：ArrayList的构造函数：ArrayList的构造函数源码有三种：先来看看ArrayList底层定义的一些变量的含义：/**Defaultinitialcapacity*默认的容量大小*/privatestaticfinalintDEFAULT_CAPACITY=10;/**Sharedemptyarrayinstanceusedforempty... 查看详情
hashmap底层实现原理
一、jdk1.7中HashMap的底层实现原理首先，当我们通过HashMap的构造方法创建一个HashMap对象时，底层就会创建一个Entry类型的一维数组（默认初始化长度为16）。当我们执行put操作的时候，会调用key所属类的hashCode方法计算出key的hash... 查看详情
浅谈java集合丨底层源码解析
...种经常用的Map、List、Set。1、Map一、背景二、Map家族三、HashMap、Hashtable等四、HashMap底层数据结构2、List一、List 包括的子类二、ArrayList三、ArrayList 源码分析四、LinkedList五、Linked 查看详情
（转）hashmap底层实现原理
①HashMap的工作原理HashMap基于hashing原理，我们通过put()和get()方法储存和获取对象。当我们将键值对传递给put()方法时，它调用键对象的hashCode()方法来计算hashcode，让后找到bucket位置来储存值对象。当获取对象时，通过键对象... 查看详情
hashmap底层原理分析（putget方法）(代码片段)
1、HashMap底层原理分析（put、get方法）HashMap底层是通过数组加链表的结构来实现的。HashMap通过计算key的hashCode来计算hash值，只要hashCode一样，那hash值就是相同的。当hash值相同时，就会出现hash冲突，HashMap通过链表来解决冲... 查看详情
hashmap的底层原理
...明存储结构:既然是线性数组，为什么能随机存取？这里HashMap用了一个小算法，大致是这样实现：//存储时: inthash=key.hashCode();//这个hashCode方法这里不详述,只要理解每个key的hash是一个固定的int值 intindex=hash%Entry[].length; ... 查看详情
hashmap的底层原理实现
...———————— 众所周知，HashMap是一个用于存储Key-Value键值对的集合，每一个键值对也叫做Entry。这些个键值对（Entry）分散存储在一个数组当中，这个数组就是HashMap的主干。HashMap数组每一个元素... 查看详情
hashmap与hashtable的区别以及hashmap的底层原理
1.区别：（1）HashMap没有synchronized修饰，线程是不安全的，建议使用ConcurrentHashMap；而HashTable是线程安全的，但是效率很低（2）HashMap允许key和value为null，而HashTable不允许2.HashMap的底层实现：数组加链表从jdk8开始，当链表的高度达... 查看详情
作为java开发，知道hashmap底层存储原理总不会害你！
HashMap底层存储原理概念存储的优点HashMap存储元素的过程HashMap取值的实现扩容HashMap中的扩容是在元素插入之前进行的扩容还是元素插入之后进行的扩容存储元素超过阈... 查看详情
java面试题hashmap的底层实现原理(代码片段)
描述HashMap的底层实现原理HashMap:作为Map的主要实现类；线程不安全的，效率高；存储null的key和valueHashMap在jdk7中的底层实现原理：HashMapmap=newHashMap():在实例化以后，底层创建了长度是16的一维数组Entry[]table。... 查看详情
hashmap底层实现原理
一、数据结构HashMap中的数据结构是数组+单链表的组合，以键值对(key-value)的形式存储元素的，通过put()和get()方法储存和获取对象。（方块表示Entry对象，横排表示数组table[]，纵排表示哈希桶bucket【实际上是一个由Entry组成的链... 查看详情
hashmap的底层实现原理
1.线性链表->数组+链表--------HashMap是数组结构、链表结构与Hash算法的结合。如图所示： Hash算法中 Object.hashcode() 计算出Object的哈希码值(int) 同一个对象多次调用hashcode()得到的结构都是相同的 两个对象调用equ... 查看详情
java面试题hashmap的底层原理和线程安全的替代方案(代码片段)
HashMap的底层原理1、HashMap底层数据结构1.1、JDK1.7和JDK1.8中HashMap的重大区别（很重要）1.2、JDK1.8中HashMap涉及的数据结构1.3、JDK1.8为什么会引入红黑树？2、HashMap的主要参数都有哪些？3、HashMap的存取原理（put和ge... 查看详情
理解hashmap底层原理，一个简单的hashmap例子(代码片段)
packagecom.jl.testmap;/***自定义一个HashMap*@authorJiangLai**/publicclassMyHashMap<K,V>Node<K,V>[]table;//位桶数组intsize;//存放键值对的个数publicMyHashMap()table=newNode[16];//长度一般定义为2的整数次幂publicvoidpu 查看详情
深度解剖hashmap底层原理(代码片段)
HashMap底层原理写在前面JDK1.7版本——HashMapjava.1.7源码分析new一个HashMap实例的存储流程图如下：API常用方法API中重要的变量第一步：申明一个HashMap对象第二步：存放键值对，put()方法第三步：获取数据get()对Hash... 查看详情