`
zha_zi
  • 浏览: 592570 次
  • 性别: Icon_minigender_1
  • 来自: 西安
社区版块
存档分类
最新评论

hash算法 (hashmap 实现原理)

 
阅读更多

 

     Hash ,一般翻译做 散列 ,也有直接音译为 哈希 的,就是把任意长度的输入(又叫做预映射, pre-image ),通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是,散列值的空间通常远小于输入的空间,不 同的输入可能会散列成相同的输出,而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

HASH 主要用于信息安全领域中加密算法,它把一些不同长度的信息转化成杂乱的128 位的编码, 这些编码值叫做HASH. 也可以说,hash 就是找到一种数据内容和数据存放地址之间的映射关系

例如字符串 hello 的哈希算法

char* value = "hello"; int key = (((((((27* (int)'h'+27)* (int)'e') + 27)  * (int)'l') + 27) * (int)'l' +27) * 27 ) + (int)'o' ;

 

  数组的特点是:寻址容易,插入和删除困难;而链表的特点是:寻址困难,插入和删除容易。那么我们能不能综合两者的特性,做出一种寻址容易,插入删除也容易 的数据结构?答案是肯定的,这就是我们要提起的哈希表,哈希表有多种不同的实现方法,我接下来解释的是最常用的一种方法—— 拉链法,我们可以理解为 链表 的数组 ,如图:


 

 

 

HashMap其实也是一个线性的数组实现的,所以可以理解为其存储数据的容器就是一个线性数组。这可能让我们很不解,一个线性的数组怎么实现按键值对来存取数据呢?这里HashMap有做一些处理。

    1.首先HashMap里面实现一个静态内部类Entry 其重要的属性有 key , value, next,从属性key,value我们就能很明显的看出来Entry就是HashMap键值对实现的一个基础bean,我们上面说到HashMap的基 础就是一个线性数组,这个数组就是Entry[],Map里面的内容都保存在Entry[]里面。

     2.既然是线性数组,为什么能随机存取?这里HashMap用了一个小算法,大致是这样实现:

 

存储时:

int hash = key.hashCode();--> 这个hashCode方法这里不详述,只要理解每个key的hash是一个固定的int值

int index = hash % Entry[].length;

Entry[index] = value;

取值时:

int hash = key.hashCode();

int index = hash % Entry[].length;

return Entry[index]
 

到这里我们轻松的理解了HashMap通过键值对实现存取的基本原理

    3.疑问:如果两个key通过hash % Entry[].length得到的index相同,会不会有覆盖的危险?

这里HashMap里面用到链式数据结构的一个概念.上面我们提到过Entry类里面有一个next属性,作用是指向下一个Entry。打个比方, 第一个键值对A进来,通过计算其key的hash得到的index=0,记做:Entry[0] = A.一会后又进来一个键值对B,通过计算其index也等于0,现在怎么办?HashMap会这样做:B.next = A,Entry[0] = B,如果又进来C,index也等于0,那么C.next = B,Entry[0] = C;这样我们发现index=0的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起。所以疑问不用担心。

到这里为止,HashMap的大致实现,我们应该已经清楚了。

当然HashMap里面也包含一些优化方面的实现,这里也啰嗦一下。

比如:Entry[]的长度一定后,随着map里面数据的越来越长,这样同一个index的链就会很长,会不会影响性能?

HashMap里面设置一个因素(也称为因子),随着map的size越来越大,Entry[]会以一定的规则加长长度。

 

 

解决hash冲突的办法

1)开放定址法(线性探测再散列,二次探测再散列,伪随机探测再散列)

2)再哈希法

3)链地址法

4)建立一 公共溢出区

 

java 中hashmap的解决办法就是采用的链地址法

 

  • 大小: 49 KB
分享到:
评论
4 楼 渭水的一只 2017-02-07  
                     
3 楼 tinybeats 2016-07-20  
huoshouyu 写道
想问下,第三点中提到,对于键值相同的,数据会以链表的形式存储在后面,获取的时候,怎么知道获取哪个数值?

键值如果相同,entry的value肯定会被覆盖掉,见如下代码:
if ((e.hash == hash) && e.key.equals(key)) {
                V old = e.value;
                e.value = value;
                return old;
            }
lz的意思是如果通过(hash & 0x7FFFFFFF) % tab.length得到的entry数组索引位相同,则会将新的key value 在此数组位置上置顶插入
2 楼 lsqldfdfd 2016-01-13  
huoshouyu 写道
想问下,第三点中提到,对于键值相同的,数据会以链表的形式存储在后面,获取的时候,怎么知道获取哪个数值?


如果寻址到当前key所在的下标存储形式是链表结构,通过遍历链表结构,判断hash值+key值是否相等,如果相等,返回当前Entry的value。

见HashMap源码
        int hash = 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.equals(k)))
                return e.value;
        }
1 楼 huoshouyu 2016-01-08  
想问下,第三点中提到,对于键值相同的,数据会以链表的形式存储在后面,获取的时候,怎么知道获取哪个数值?

相关推荐

    rust使用的自定义哈希算法(加上 hashmap/set 别名):快速、确定性_rust_代码_下载

    liballoc 中的 hashmap 默认使用 SipHash,它并没有我们想要的那么快。在编译器中,我们并不真正担心 DOS 尝试,因此我们使用快速非加密哈希。 这与 Firefox 使用的算法相同——它是一种不基于任何广为人知的算法的...

    HashMap的实现原理

    ### HashMap的实现原理 #### 1. HashMap概述 HashMap 是 Java 集合框架中一个非常重要的类,它实现了 Map 接口,并提供了基于哈希表的存储方式。与其它 Map 实现不同的是,HashMap 允许使用 `null` 键和 `null` 值...

    HashMap-hash原理

    本文将重点解析`HashMap`中hash算法的核心原理及其优化细节。 #### 二、计算Key的HashCode `HashMap`在存储数据时首先需要计算出每个键(key)对应的哈希码(hashCode)。这个过程通常通过调用对象自身的`hashCode...

    HashMap原理的深入理解

    HashMap原理的深入理解 HashMap是基于哈希表的Map接口的非同步实现,提供了所有可选的映射操作,并允许使用null值和null键。HashMap储存的是键值对,HashMap很快。此类不保证映射的顺序,特别是它不保证该顺序恒久...

    HashMap底层实现原理共6页.pdf.zip

    HashMap在Java中的实现原理主要包括数组和链表两种数据结构的结合,以及对哈希算法的应用。 1. 哈希表基础 HashMap的核心是一个动态调整大小的哈希表,也称为散列表。哈希表通过将键(key)转换为一个哈希码(hash ...

    HashMap扩容时的rehash方法中(e.hash & oldCap) == 0算法推导.docx

    在Java的集合框架中,HashMap是一种常用的键值对存储结构,它通过哈希表实现高效的数据查找、插入和删除操作。当HashMap达到其容量阈值并需要扩容时,会触发一个内部称为`rehash`的过程。这个过程涉及到将旧数组中的...

    HashMap底层原理.pdf

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

    用hashmap实现词典查询

    首先,我们来深入理解HashMap的工作原理。HashMap基于哈希表的概念,它通过计算元素的哈希码(hash code)将键(key)映射到数组的特定位置。当查找某个键时,HashMap会先计算键的哈希码,然后使用这个哈希码找到...

    HashMap原理.docx

    ### HashMap原理详解 #### 一、HashMap简介与应用场景 HashMap是Java集合框架中一个非常重要的组成部分,它提供了基于键值对(key-value)映射的高效数据存储方式。由于其内部采用了数组加链表(以及红黑树优化)的...

    各种hash算法-hashcodeUtil

    本篇文章将深入探讨各种Hash算法,并以`hashCodeUtil`为例,解析其在实际应用中的实现和用途。 首先,我们来了解一些基本的Hash算法。MD5(Message-Digest Algorithm 5)和SHA(Secure Hash Algorithm)家族是常见...

    java 集合和泛型 1. Map接口 2. HashMap底层实现 3. Hash数据结构和算法 4. 红黑树数据结构和算法

    java 集合和泛型 1. Map接口 2. HashMap底层实现 3. Hash数据结构和算法 4. 红黑树数据结构和算法

    hashmap中hash函数的构造问题

    本文将深入探讨`HashMap`中几种典型的哈希函数构造方法,并通过示例代码来帮助读者理解这些函数的工作原理。 #### 二、基础知识 在深入了解具体的哈希函数之前,我们先回顾一下哈希表的基本概念: - **哈希表**:...

    Java HashMap类详解

    本资源详细介绍了 Java 中的 HashMap 类,包括其实现机制、Hash 存储机制、集合存储机制等方面的知识点。 1. HashMap 和 HashSet 的关系 HashMap 和 HashSet 是 Java Collection Framework 的两个重要成员,虽然...

    ConsistentHash:一致性hash算法的 java 和 C++ 实现

    在这个场景下,我们将深入探讨一致性哈希算法的原理、特点以及在Java和C++中的实现。 一致性哈希算法的基本思想是将哈希空间环绕成一个虚拟的圆环,每个节点都被分配到这个环上的一个或多个位置。当需要将数据映射...

    HASH_hash_stm32hash_stm32hash表_stm32f407_

    在STM32F407上实现的哈希(Hash)算法是数字签名、数据完整性验证等安全应用中的关键组成部分。哈希算法能够将任意长度的输入数据转化为固定长度的输出,通常称为哈希值或消息摘要。 哈希算法的主要特性包括: 1. *...

    HashMap工作原理_动力节点Java学院整理

    HashMap 工作原理 HashMap 是 Java 中一种常用的数据结构,它可以存储大量的 key-value 对,并且提供...HashMap 的工作原理是基于 Hash 算法的,它可以快速存储和查找大量的 key-value 对,从而提高程序的效率和性能。

    HashMap-master.zip_hash

    HashMap在Java编程语言中的实现是`java.util.HashMap`类,它是基于哈希表原理来工作的。标题"HashMap-master.zip_hash"可能指的是一个关于HashMap实现或优化的项目,其中包含了哈希函数的设计和分析。 哈希表的核心...

    uthash开源的hash函数实现

    虽然 UTHASH 内部实现的具体哈希算法未公开,但其目标是尽可能均匀地分布数据,以减少冲突。 2. **宏定义**:UTHASH 提供了一系列的宏定义,例如 `UT_hash_handle`,它需要附加到你的结构体定义上,以启用哈希功能...

    HashMap介绍和使用

    ### HashMap介绍和使用详解 #### 一、HashMap的数据结构 HashMap是Java集合框架的一个重要组成部分,它实现了Map接口,能够存储键值对映射。...理解HashMap的工作原理对于优化Java程序的性能具有重要意义。

Global site tag (gtag.js) - Google Analytics