`
tianlijia202
  • 浏览: 78622 次
  • 性别: Icon_minigender_1
  • 来自: 大连
社区版块
存档分类
最新评论

HashMap 结构

    博客分类:
  • java
 
阅读更多

文章出处:

http://java.chinaitlab.com/base/879452.html

 

1.HashMap概述

    HashMap是基于哈希表的Map接口的非同步实现。此实现提供所有可选的映射操作,并允许使用null值和null键。此类不保证映射的顺序,特别是它不保证该顺序恒久不变。

    2.HashMap的数据结构

    在java编程语言中,最基本的结构就是两种,一个是数组,另外一个是模拟指针(引用),所有的数据结构都可以用这两个基本结构来构造的,HashMap也不例外。HashMap实际上是一个“链表散列”的数据结构,即数组和链表的结合体。

    3.HashMap的存取

    HashMap的功能是通过“键(key)”能够快速的找到“值”。下面我们分析下HashMap存数据的基本流程:

    1、 当调用put(key,value)时,首先获取key的hashcode,int hash = key.hashCode();

    2、 再把hash通过一下运算得到一个int h.

    hash ^= (hash >>> 20) ^ (hash >>> 12);

    int h = hash ^ (hash >>> 7) ^ (hash >>> 4);

    为什么要经过这样的运算呢?这就是HashMap的高明之处。先看个例子,一个十进制数32768(二进制1000 0000 0000 0000),经过上述公式运算之后的结果是35080(二进制1000 1001 0000 1000)。看出来了吗?或许这样还看不出什么,再举个数字61440(二进制1111 0000 0000 0000),运算结果是65263(二进制1111 1110 1110 1111),现在应该很明显了,它的目的是让“1”变的均匀一点,散列的本意就是要尽量均匀分布。那这样有什么意义呢?看第3步。

    3、 得到h之后,把h与HashMap的承载量(HashMap的默认承载量length是16,可以自动变长。在构造HashMap的时候也可以指定一个长 度。这个承载量就是上图所描述的数组的长度。)进行逻辑与运算,即 h & (length-1),这样得到的结果就是一个比length小的正数,我们把这个值叫做index。其实这个index就是索引将要插入的值在数组中的 位置。第2步那个算法的意义就是希望能够得出均匀的index,这是HashTable的改进,HashTable中的算法只是把key的 hashcode与length相除取余,即hash % length,这样有可能会造成index分布不均匀。还有一点需要说明,HashMap的键可以为null,它的值是放在数组的第一个位置。

    4、 我们用table[index]表示已经找到的元素需要存储的位置。先判断该位置上有没有元素(这个元素是HashMap内部定义的一个类Entity, 基本结构它包含三个类,key,value和指向下一个Entity的next),没有的话就创建一个Entity<K,V>对象,在 table[index]位置上插入,这样插入结束;如果有的话,通过链表的遍历方式去逐个遍历,看看有没有已经存在的key,有的话用新的value替 换老的value;如果没有,则在table[index]插入该Entity,把原来在table[index]位置上的Entity赋值给新的 Entity的next,这样插入结束。

    总结:keyàhashcodeàhàindexà遍历链表à插入

    4.扩展问题

    要同时复写equals方法和hashCode方法。

    按照散列函数的定义,如果两个对象相同,即obj1.equals(obj2)=true,则它们的hashCode必须相同,但如果两个对象不同,则它们的hashCode不一定不同。

    如果两个不同对象的hashCode相同,这种现象称为冲突,冲突会导致操作哈希表的时间开销增大,所以尽量定义好的hashCode()方法,能加快哈希表的操作。

    如果相同的对象有不同的hashCode,对哈希表的操作会出现意想不到的结果(期待的get方法返回null),

    再回头看看前面提到的为什么覆盖了equals方法之后一定要覆盖hashCode方法,很简单,比如,String a = new String(“abc”);String b = new String(“abc”);如果不覆盖hashCode的话,那么a和b的hashCode就会不同,把这两个类当做key存到HashMap中的话就 会出现问题,就会和key的唯一性相矛盾

分享到:
评论

相关推荐

    HASHMAP结构及版本区别.docx

    HashMap是Java编程语言中一种非常重要的数据结构,用于存储键值对。它继承自AbstractMap,并实现了Map、Cloneable和Serializable接口。HashMap的核心特点是通过key的哈希值来快速定位value,提供高效的插入、查找和...

    HashMap的数据结构

    HashMap是Java编程语言中一个非常重要的数据结构,它属于集合框架的一部分,主要用于存储键值对(Key-Value)数据。HashMap在内部实现上基于哈希表,也称为散列表,它提供了一种快速查找、插入和删除数据的方法,...

    源码解析jdk8.0集合:HashMap的底层实现原理.pdf

    - modCount:HashMap结构修改的计数器。 在JDK 8.0版本中,HashMap内部实现了懒惰初始化,也就是说只有在第一次使用时才会初始化数组table。当使用put方法插入键值对时,如果键对应的哈希值没有冲突,直接放到数组...

    Jdk1.8中的HashMap实现原理.docx

    此外,HashMap中的size字段记录了当前存储的键值对数量,而modCount则用于跟踪HashMap结构的变化,用于实现迭代器的快速失败机制,当HashMap在迭代过程中被修改时,迭代器能够立即抛出异常,避免不一致的结果。...

    Jdk1.8中的HashMap实现原理.pdf

    `modCount`记录HashMap结构变化的次数,用于迭代器的快速失败机制;`size`表示当前HashMap中存储的键值对数量。 扩容机制是HashMap性能的关键。当HashMap中的键值对数量达到`threshold`时,HashMap会进行扩容,将...

    javaScript模拟的HashMap数据结构的对象

    javaScript模拟的HashMap数据结构,可以方便的put和get。几乎和Java中HashMap类的功能一模一样。非常好用的!

    比较分析Vector、ArrayList和hashtable hashmap数据结构

    比较分析Vector、ArrayList和hashtable hashmap数据结构

    2022年Java中对HashMap的深度分析Java教程.docx

    在HashMap的实现中,还有一个重要的概念是modCount,用于记录HashMap结构变更的次数,这在并发控制和迭代器的正确性中起到关键作用。 HashMap的get方法同样依赖于键的hashCode。给定一个键,get方法会计算哈希值并...

    HashMap的一个数据结构

    HashMap的一个数据结构 锁升级:锁升级过程 resize的过程在开发中 怎么保证容器它线程安全后就是数据插入过程使用的头插法 但是头插法会造成一些问题等等等等的那个等等的那个等等的那个等等的那个等等的那个等等的...

    hashmap面试题_hashmap_

    HashMap作为Java集合框架中的重要成员,是面试中常见的知识点,尤其在数据结构与算法、并发编程以及JVM内存管理等领域,HashMap的深入理解至关重要。本篇将围绕HashMap的相关面试题,从基础概念到高级应用进行详尽...

    【考研】数据结构习题总结.pdf

    4. HashMap结构:HashMap在Java中是通过数组加链表实现的,数组部分用于快速访问元素,链表部分用于解决哈希冲突。 5. 栈:栈是一种后进先出(LIFO)的数据结构,文档描述了如何将一个数组空间分配给两个栈使用,...

    sesvc.exe 阿萨德

    开始的时候就提到 HashMap 是由数组和链表组成,所以这个 next 就是用于实现链表结构。 hash 存放的是当前 key 的 hashcode。 知晓了基本结构,那来看看其中重要的写入、获取函数: put 方法 public V put(K key, V...

    HashMap介绍和使用

    所有的复杂数据结构都可以基于这两种基本结构构建出来,HashMap也不例外。 **1.1 数组和链表结合** HashMap内部采用数组加链表(或红黑树)的形式存储数据,这种结构称为“链表散列”。数组作为主存储结构,而链表...

    详解JavaScript中Hash Map映射结构的实现_.docx

    本文将深入探讨如何在JavaScript中实现一个简单的HashMap结构,并讨论与`Object`相关的陷阱。 首先,我们来看一个简单的HashMap实现: ```javascript var hashMap = { Set: function(key, value) { this[key] = ...

    关于如何解决HashMap线程安全问题的介绍

    例如,当一个线程正在执行put操作时,另一个线程可能同时在进行get或remove操作,这可能导致HashMap内部结构的混乱。 2. resize()方法的问题:HashMap在容量达到阈值时会进行扩容操作,这个过程中需要重新计算键的...

    深入探讨HashMap的底层结构、原理、扩容机制.pdf

    深入探讨HashMap的底层结构、原理、扩容机制,

    HashMap底层原理.pdf

    HashMap是Java中非常常见的一种数据结构,主要用于存储键值对,其核心原理是通过哈希算法将键映射到数组中的位置来实现快速访问。本文将详细介绍HashMap的底层原理,包括其内部实现结构、关键字段的作用、以及JDK ...

    hashmap 实例

    《HashMap 实例解析与关联数据结构对比》 HashMap 是 Java 中常用的一种数据结构,属于 Java.util 包下的类,它是基于哈希表实现的。在本文中,我们将深入理解 HashMap 的实例及其工作原理,并与其他数据结构如 ...

    hashmap实现原理

    哈希映射(HashMap)是Java编程语言中广泛使用的数据结构之一,主要提供键值对的存储和查找功能。HashMap的实现基于哈希表的概念,它通过计算对象的哈希码来快速定位数据,从而实现了O(1)的平均时间复杂度。在深入...

    Hashmap详解

    HashMap 是一种常用的数据结构,在 Java 中,它是一个数组和链表的结合体。下面我们将深入探讨 HashMap 的数据结构、 put 方法的实现细节和 Hash 码的计算过程。 HashMap 的数据结构 HashMap 的数据结构可以分为两...

Global site tag (gtag.js) - Google Analytics