HashMap的实现原理和底层数据结构

article/2025/11/9 12:52:32

看了下JAVA里面有HashMap、Hashtable、HashSet三种hash集合的实现源码，这里总结下，理解错误的地方还望指正

HashMap和Hashtable的区别

HashSet和HashMap、Hashtable的区别

HashMap和Hashtable的实现原理

HashMap的简化实现MyHashMap

 

HashMap和Hashtable的区别

  1. 两者最主要的区别在于Hashtable是线程安全，而HashMap则非线程安全
    Hashtable的实现方法里面都添加了synchronized关键字来确保线程同步，因此相对而言HashMap性能会高一些，我们平时使用时若无特殊需求建议使用HashMap，在多线程环境下若使用HashMap需要使用Collections.synchronizedMap()方法来获取一个线程安全的集合（Collections.synchronizedMap()实现原理是Collections定义了一个SynchronizedMap的内部类，这个类实现了Map接口，在调用方法时使用synchronized来保证线程同步,当然了实际上操作的还是我们传入的HashMap实例，简单的说就是Collections.synchronizedMap()方法帮我们在操作HashMap时自动添加了synchronized来实现线程同步，类似的其它Collections.synchronizedXX方法也是类似原理）
  2. HashMap可以使用null作为key，而Hashtable则不允许null作为key
    虽说HashMap支持null值作为key，不过建议还是尽量避免这样使用，因为一旦不小心使用了，若因此引发一些问题，排查起来很是费事
    HashMap以null作为key时，总是存储在table数组的第一个节点上
  3. HashMap是对Map接口的实现，HashTable实现了Map接口和Dictionary抽象类
  4. HashMap的初始容量为16，Hashtable初始容量为11，两者的填充因子默认都是0.75
    HashMap扩容时是当前容量翻倍即:capacity*2，Hashtable扩容时是容量翻倍+1即:capacity*2+1
  5. 两者计算hash的方法不同
    Hashtable计算hash是直接使用key的hashcode对table数组的长度直接进行取模
    int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;

    HashMap计算hash对key的hashcode进行了二次hash，以获得更好的散列值，然后对table数组长度取摸

    复制代码 
    static int hash(int h) {// This function ensures that hashCodes that differ only by// constant multiples at each bit position have a bounded// number of collisions (approximately 8 at default load factor).h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4);}static int indexFor(int h, int length) {return h & (length-1);}
    复制代码

     

  6. HashMap和Hashtable的底层实现都是数组+链表结构实现

HashSet和HashMap、Hashtable的区别

除开HashMap和Hashtable外，还有一个hash集合HashSet，有所区别的是HashSet不是key value结构，仅仅是存储不重复的元素，相当于简化版的HashMap，只是包含HashMap中的key而已

通过查看源码也证实了这一点，HashSet内部就是使用HashMap实现，只不过HashSet里面的HashMap所有的value都是同一个Object而已，因此HashSet也是非线程安全的，至于HashSet和Hashtable的区别，HashSet就是个简化的HashMap的，所以你懂的
下面是HashSet几个主要方法的实现

复制代码 
  private transient HashMap<E,Object> map;
  private static final Object PRESENT = new Object();public HashSet() {map = new HashMap<E,Object>();}public boolean contains(Object o) {return map.containsKey(o);}public boolean add(E e) {return map.put(e, PRESENT)==null;}public boolean add(E e) {return map.put(e, PRESENT)==null;}public boolean remove(Object o) {return map.remove(o)==PRESENT;}public void clear() {map.clear();}
复制代码

 

HashMap和Hashtable的实现原理

HashMap和Hashtable的底层实现都是数组+链表结构实现的，这点上完全一致

添加、删除、获取元素时都是先计算hash，根据hash和table.length计算index也就是table数组的下标，然后进行相应操作，下面以HashMap为例说明下它的简单实现

复制代码 
  /*** HashMap的默认初始容量 必须为2的n次幂*/static final int DEFAULT_INITIAL_CAPACITY = 16;/*** HashMap的最大容量，可以认为是int的最大值    */static final int MAXIMUM_CAPACITY = 1 << 30;/*** 默认的加载因子*/static final float DEFAULT_LOAD_FACTOR = 0.75f;/*** HashMap用来存储数据的数组*/transient Entry[] table;
复制代码
  • HashMap的创建
    HashMap默认初始化时会创建一个默认容量为16的Entry数组，默认加载因子为0.75，同时设置临界值为16*0.75
    复制代码 
        /*** Constructs an empty <tt>HashMap</tt> with the default initial capacity* (16) and the default load factor (0.75).*/public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR;threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);table = new Entry[DEFAULT_INITIAL_CAPACITY];init();}
    复制代码

     

  • put方法
    HashMap会对null值key进行特殊处理，总是放到table[0]位置
    put过程是先计算hash然后通过hash与table.length取摸计算index值，然后将key放到table[index]位置，当table[index]已存在其它元素时，会在table[index]位置形成一个链表，将新添加的元素放在table[index]，原来的元素通过Entry的next进行链接，这样以链表形式解决hash冲突问题，当元素数量达到临界值(capactiy*factor)时，则进行扩容，是table数组长度变为table.length*2
  • 复制代码 
     public V put(K key, V value) {if (key == null)return putForNullKey(value); //处理null值int hash = hash(key.hashCode());//计算hashint i = indexFor(hash, table.length);//计算在数组中的存储位置//遍历table[i]位置的链表，查找相同的key，若找到则使用新的value替换掉原来的oldValue并返回oldValuefor (Entry<K,V> e = table[i]; e != null; e = e.next) {Object k;if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {V oldValue = e.value;e.value = value;e.recordAccess(this);return oldValue;}}//若没有在table[i]位置找到相同的key，则添加key到table[i]位置，新的元素总是在table[i]位置的第一个元素，原来的元素后移modCount++;addEntry(hash, key, value, i);return null;}void addEntry(int hash, K key, V value, int bucketIndex) {//添加key到table[bucketIndex]位置，新的元素总是在table[bucketIndex]的第一个元素，原来的元素后移Entry<K,V> e = table[bucketIndex];table[bucketIndex] = new Entry<K,V>(hash, key, value, e);//判断元素个数是否达到了临界值，若已达到临界值则扩容，table长度翻倍if (size++ >= threshold)resize(2 * table.length);}
    复制代码

     

  • get方法
    同样当key为null时会进行特殊处理，在table[0]的链表上查找key为null的元素
    get的过程是先计算hash然后通过hash与table.length取摸计算index值，然后遍历table[index]上的链表，直到找到key，然后返回
    复制代码 
    public V get(Object key) {if (key == null)return getForNullKey();//处理null值int hash = hash(key.hashCode());//计算hash//在table[index]遍历查找key，若找到则返回value，找不到返回nullfor (Entry<K,V> e = table[indexFor(hash, table.length)];e != null;e = e.next) {Object k;if (e.hash == hash && ((k = e.key) == key || key.equals(k)))return e.value;}return null;}
    复制代码

     

  • remove方法
    remove方法和put get类似，计算hash，计算index，然后遍历查找，将找到的元素从table[index]链表移除
    复制代码 
        public V remove(Object key) {Entry<K,V> e = removeEntryForKey(key);return (e == null ? null : e.value);}final Entry<K,V> removeEntryForKey(Object key) {int hash = (key == null) ? 0 : hash(key.hashCode());int i = indexFor(hash, table.length);Entry<K,V> prev = table[i];Entry<K,V> e = prev;while (e != null) {Entry<K,V> next = e.next;Object k;if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k)))) {modCount++;size--;if (prev == e)table[i] = next;elseprev.next = next;e.recordRemoval(this);return e;}prev = e;e = next;}return e;}
    复制代码

     

  • resize方法
    resize方法在hashmap中并没有公开，这个方法实现了非常重要的hashmap扩容，具体过程为：先创建一个容量为table.length*2的新table，修改临界值，然后把table里面元素计算hash值并使用hash与table.length*2重新计算index放入到新的table里面
    这里需要注意下是用每个元素的hash全部重新计算index，而不是简单的把原table对应index位置元素简单的移动到新table对应位置
    复制代码 
    void resize(int newCapacity) {Entry[] oldTable = table;int oldCapacity = oldTable.length;if (oldCapacity == MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return;}Entry[] newTable = new Entry[newCapacity];transfer(newTable);table = newTable;threshold = (int)(newCapacity * loadFactor);}void transfer(Entry[] newTable) {Entry[] src = table;int newCapacity = newTable.length;for (int j = 0; j < src.length; j++) {Entry<K,V> e = src[j];if (e != null) {src[j] = null;        do {Entry<K,V> next = e.next;
                        //重新对每个元素计算index     int i = indexFor(e.hash, newCapacity);e.next = newTable[i];newTable[i] = e;e = next;} while (e != null);}}}
    复制代码

     

  • clear()方法
    clear方法非常简单，就是遍历table然后把每个位置置为null，同时修改元素个数为0
    需要注意的是clear方法只会清楚里面的元素，并不会重置capactiy
    复制代码 
     public void clear() {modCount++;Entry[] tab = table;for (int i = 0; i < tab.length; i++)tab[i] = null;size = 0;}
    复制代码

     

  • containsKey和containsValue
    containsKey方法是先计算hash然后使用hash和table.length取摸得到index值，遍历table[index]元素查找是否包含key相同的值
    复制代码 
    public boolean containsKey(Object key) {return getEntry(key) != null;}
final Entry<K,V> getEntry(Object key) {int hash = (key == null) ? 0 : hash(key.hashCode());for (Entry<K,V> e = table[indexFor(hash, table.length)];e != null;e = e.next) {Object k;if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;}return null;}
    复制代码

    containsValue方法就比较粗暴了，就是直接遍历所有元素直到找到value，由此可见HashMap的containsValue方法本质上和普通数组和list的contains方法没什么区别，你别指望它会像containsKey那么高效

    复制代码 
    public boolean containsValue(Object value) {if (value == null)return containsNullValue();Entry[] tab = table;for (int i = 0; i < tab.length ; i++)for (Entry e = tab[i] ; e != null ; e = e.next)if (value.equals(e.value))return true;return false;}
    复制代码

     

  • hash和indexFor
    indexFor中的h & (length-1)就相当于h%length，用于计算index也就是在table数组中的下标
    hash方法是对hashcode进行二次散列，以获得更好的散列值
    为了更好理解这里我们可以把这两个方法简化为 int index= key.hashCode()/table.length,以put中的方法为例可以这样替换
    int hash = hash(key.hashCode());//计算hash
int i = indexFor(hash, table.length);//计算在数组中的存储位置
//上面这两行可以这样简化
int i = key.key.hashCode()%table.length;

     

  • 复制代码 
      static int hash(int h) {// This function ensures that hashCodes that differ only by// constant multiples at each bit position have a bounded// number of collisions (approximately 8 at default load factor).h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4);}static int indexFor(int h, int length) {return h & (length-1);}
    复制代码

     

HashMap的简化实现MyHashMap

为了加深理解，我个人实现了一个简化版本的HashMap，注意哦，仅仅是简化版的功能并不完善，仅供参考

复制代码 
package cn.lzrabbit.structure;/*** Created by rabbit on 14-5-4.*/
public class MyHashMap {//默认初始化大小 16private static final int DEFAULT_INITIAL_CAPACITY = 16;//默认负载因子 0.75private static final float DEFAULT_LOAD_FACTOR = 0.75f;//临界值private int threshold;//元素个数private int size;//扩容次数private int resize;private HashEntry[] table;public MyHashMap() {table = new HashEntry[DEFAULT_INITIAL_CAPACITY];threshold = (int) (DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);size = 0;}private int index(Object key) {//根据key的hashcode和table长度取模计算key在table中的位置return key.hashCode() % table.length;}public void put(Object key, Object value) {//key为null时需要特殊处理，为简化实现忽略null值if (key == null) return;int index = index(key);//遍历index位置的entry，若找到重复key则更新对应entry的值，然后返回HashEntry entry = table[index];while (entry != null) {if (entry.getKey().hashCode() == key.hashCode() && (entry.getKey() == key || entry.getKey().equals(key))) {entry.setValue(value);return;}entry = entry.getNext();}//若index位置没有entry或者未找到重复的key，则将新key添加到table的index位置
        add(index, key, value);}private void add(int index, Object key, Object value) {//将新的entry放到table的index位置第一个，若原来有值则以链表形式存放HashEntry entry = new HashEntry(key, value, table[index]);table[index] = entry;//判断size是否达到临界值，若已达到则进行扩容，将table的capacicy翻倍if (size++ >= threshold) {resize(table.length * 2);}}private void resize(int capacity) {if (capacity <= table.length) return;HashEntry[] newTable = new HashEntry[capacity];//遍历原table，将每个entry都重新计算hash放入newTable中for (int i = 0; i < table.length; i++) {HashEntry old = table[i];while (old != null) {HashEntry next = old.getNext();int index = index(old.getKey());old.setNext(newTable[index]);newTable[index] = old;old = next;}}//用newTable替tabletable = newTable;//修改临界值threshold = (int) (table.length * DEFAULT_LOAD_FACTOR);resize++;}public Object get(Object key) {//这里简化处理，忽略null值if (key == null) return null;HashEntry entry = getEntry(key);return entry == null ? null : entry.getValue();}public HashEntry getEntry(Object key) {HashEntry entry = table[index(key)];while (entry != null) {if (entry.getKey().hashCode() == key.hashCode() && (entry.getKey() == key || entry.getKey().equals(key))) {return entry;}entry = entry.getNext();}return null;}public void remove(Object key) {if (key == null) return;int index = index(key);HashEntry pre = null;HashEntry entry = table[index];while (entry != null) {if (entry.getKey().hashCode() == key.hashCode() && (entry.getKey() == key || entry.getKey().equals(key))) {if (pre == null) table[index] = entry.getNext();else pre.setNext(entry.getNext());//如果成功找到并删除，修改sizesize--;return;}pre = entry;entry = entry.getNext();}}public boolean containsKey(Object key) {if (key == null) return false;return getEntry(key) != null;}public int size() {return this.size;}public void clear() {for (int i = 0; i < table.length; i++) {table[i] = null;}this.size = 0;}@Overridepublic String toString() {StringBuilder sb = new StringBuilder();sb.append(String.format("size:%s capacity:%s resize:%s\n\n", size, table.length, resize));for (HashEntry entry : table) {while (entry != null) {sb.append(entry.getKey() + ":" + entry.getValue() + "\n");entry = entry.getNext();}}return sb.toString();}
}class HashEntry {private final Object key;private Object value;private HashEntry next;public HashEntry(Object key, Object value, HashEntry next) {this.key = key;this.value = value;this.next = next;}public Object getKey() {return key;}public Object getValue() {return value;}public void setValue(Object value) {this.value = value;}public HashEntry getNext() {return next;}public void setNext(HashEntry next) {this.next = next;}
}

http://chatgpt.dhexx.cn/article/5qECVG1y.shtml

相关文章

HashMap底层实现原理

HashMap底层实现原理

HashMap实现原理 1.概述 HashMap是基于哈希表的Map接口的非同步实现。元素以键值对的形式存放&#xff0c;并且允许null键和null值&#xff0c;因为key值唯一&#xff08;不能重复&#xff09;&#xff0c;因此&#xff0c;null键只有一个。另外&#xff0c;hashmap不保证元素…
阅读更多...
hashMap实现原理

hashMap实现原理

1. HashMap概述&#xff1a; HashMap是基于哈希表的Map接口的非同步实现&#xff08;Hashtable跟HashMap很像&#xff0c;唯一的区别是Hashtalbe中的方法是线程安全的&#xff0c;也就是同步的&#xff09;。此实现提供所有可选的映射操作&#xff0c;并允许使用null值和null键…
阅读更多...
HashMap的实现原理和底层结构

HashMap的实现原理和底层结构

哈希表&#xff08;hash table&#xff09;也叫散列表&#xff0c;是一种非常重要的数据结构&#xff0c;应用场景及其丰富&#xff0c;许多缓存技术&#xff08;比如memcached&#xff09;的核心其实就是在内存中维护一张大的哈希表&#xff0c;而HashMap的实现原理也常常出现…
阅读更多...
【java】HashMap底层实现原理

【java】HashMap底层实现原理

目录 一.哈希表(散列)1.什么是哈希表2.什么是哈希冲突(面试题)3.解决哈希冲突的方法(面试题)(1) 开放地址法① 线性探查②二次探查③随机探查 (2) 再哈希法(3) 链地址法(4)建立公共溢出区 二.HashMap1.HashMap的hash()算法(面试)(1)为什么不是h key.hashCode()直接返回&#x…
阅读更多...
HashMap底层实现原理解析

HashMap底层实现原理解析

一、HashMap底层实现原理解析 我们常见的有数据结构有三种结构&#xff1a; 数组结构链表结构哈希表结构 下面我们来看看各自的数据结构的特点&#xff1a; 1&#xff09;数组结构&#xff1a; 存储区间连续、内存占用严重、空间复杂度大 优点&#xff1a;随机读取和修改效…
阅读更多...
HashMap底层实现原理概述

HashMap底层实现原理概述

1. 前言 在一场面试中最能打动面试官的其实是细节&#xff0c;候选人对细节的了解程度决定了留给面试官的印象到底是“基础扎实”还是“基础薄弱”&#xff0c;如果候选人能够举一反三主动阐述自己对一些技术细节的理解和总结&#xff0c;那无疑是面试过程中的一大亮点。HashM…
阅读更多...
HashMap实现原理分析

HashMap实现原理分析

之前转载过一篇HashMap相关分析文章&#xff0c;快速链接&#xff1a;HashMap实现原理分析 既然有前辈已经将源码分析总结了出来&#xff0c;我们在继续学习研究源码实现的时候不妨借鉴借鉴前人的总结与经验~ 本文转自&#xff1a;https://blog.csdn.net/hefenglian/article/…
阅读更多...
HashMap面试，看这一篇就够了

HashMap面试，看这一篇就够了

历史热门文章&#xff1a; 七种方式教你在SpringBoot初始化时搞点事情 Java序列化的这三个坑千万要小心可以和面试官聊半个小时的volatile原理Java中七个潜在的内存泄露风险&#xff0c;你知道几个&#xff1f;JDK 16新特性一览啥&#xff1f;用了并行流还更慢了InnoDB自增原理…
阅读更多...
java中HashMap原理

java中HashMap原理

1、为什么用HashMap&#xff1f; HashMap是一个散列桶&#xff08;数组和链表&#xff09;&#xff0c;它存储的内容是键值对(key-value)映射HashMap采用了数组和链表的数据结构&#xff0c;能在查询和修改方便继承了数组的线性查找和链表的寻址修改HashMap是非synchronized&a…
阅读更多...
HashMap的实现原理

HashMap的实现原理

1. HashMap概述 HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作&#xff0c;并允许使用null值和null键。此类不保证映射的顺序&#xff0c;特别是它不保证该顺序恒久不变。 在java编程语言中&#xff0c;最基本的结构就是两种&#xff0c;一个…
阅读更多...
软件测试用例分析和用例设计

软件测试用例分析和用例设计

测试用例的概念 测试用例&#xff08;test case&#xff09;&#xff0c;也叫测试案例&#xff0c;是为了达到一个最佳的测试效果或者高效的发现软件中的隐藏错误&#xff08;缺陷&#xff09;而精心设计的包括场景步骤和数据。 通用的定义&#xff1a;是关于一个功能验证时候…
阅读更多...
软件测试用例设计练习

软件测试用例设计练习

1、完成163邮箱注册用例的编写 邮箱地址&#xff1a;6~18个字符&#xff0c;可使用字母、数字、下划线&#xff0c;需要以字母开头 密码&#xff1a;8~16个字符&#xff0c;大、小写字母、数字、标点符号&#xff0c;3种或以上组合 2、需求&#xff1a;输入三条边&#xff…
阅读更多...
软件测试用例详细规范

软件测试用例详细规范

软件测试用例详细规范 为什么编写测试用例详细测试用例模板测试用例字段介绍用例操作步骤用例预期结果&#xff1a; 测试用例录入原则&#xff1a;测试用例设计步骤测试用例案例&#xff1a;测试用例校验点&#xff1a; 为什么编写测试用例 我也不知道&#xff0c;自己百度 详…
阅读更多...
软件测试——测试用例设计方法

软件测试——测试用例设计方法

1、测试用例定义 测试用例又叫test case&#xff0c;是为某个特殊目标而编制的一组测试输入&#xff0c;执行条件以及预期结果&#xff0c;以便测试某个程序路径或核实是否满足某个特定需求。 2、测试用例的特性 有效性&#xff1a;测试用例能够被使用&#xff0c;且被不同人…
阅读更多...
接口测试用例怎么写？

接口测试用例怎么写？

测试流程 需求规格说明书--测试计划--测试用例--用例评审--开发 接口文档--接口分析--接口用例设计--评审--接口测试执行&#xff08;关注数据库&#xff09;--前后端对接 系统界面测试--测试结束 如何设计接口测试用例&#xff1f; 1.接口正常调用&#xff0c;先要能跑通…
阅读更多...
软件测试 - 用例篇

软件测试 - 用例篇

回顾上一篇博客主要内容:软件测试 - 基础篇 1: 软件测试的流程是什么? 需求分析,测试计划,测试设计/测试开发,测试执行,测试报告 需求分析 分析需求,验证需求的正确性和合理性,从需求中提取出测试项 测试计划 要考虑测试人数,测试环境,测试时间,测试设备等 测试设计/测试开发 …
阅读更多...
软件测试用例优先级,软件测试用例的优先级划分方法

软件测试用例优先级,软件测试用例的优先级划分方法

随着互联网的不断发展&#xff0c;程序员对于软件品质以及运行状况等参数关注程度也在提高&#xff0c;而今天我们就一起来了解一下&#xff0c;在划分测试用例优先级的时候都有哪些划分方法可以使用。 没有软件系统是完美的&#xff0c;任何系统都有BUGS。但是每一次得迭代都有…
阅读更多...
软件测试：测试用例

软件测试：测试用例

一、通用测试用例八要素　　1、用例编号&#xff1b;　　2、测试项目&#xff1b;　　3、测试标题&#xff1b;　　4、重要级别&#xff1b;　　5、预置条件&#xff1b;　　6、测试输入&#xff1b;　　7、操作步骤&#xff1b;　　8、预期输出 二、具体分析通用测试用例八要…
阅读更多...
【软件测试】测试用例的设计方法

【软件测试】测试用例的设计方法

文章目录 1. 测试用例的概念2. 设计测试用例的好处3. 基于需求设计测试用例3.1 功能性需求3.2 非功能性需求 4. 设计测试用例的具体方法4.1 等价类4.2 边界值4.3 错误猜测法4.4 场景设计法4.5 因果图法4.6 正交法 5. 测试用例的粒度 1. 测试用例的概念 测试用例就是测试人员向…
阅读更多...
如何写好测试用例

如何写好测试用例

目录 前言 为什么要写用例&#xff1f; 那怎么写好测试用例呢&#xff1f; 那么我们日常测试中&#xff0c;如果用xmind梳理用例结构注意哪些点呢&#xff1f; 结语 前言 经历过校招或社招的测试同学&#xff0c;都会被问到测试用例的设计、使用方法&#xff0c;以及用例的…
阅读更多...
推荐文章

Copyright @ 2022~2023