`
小野bupt
  • 浏览: 14730 次
  • 性别: Icon_minigender_1
文章分类
社区版块
存档分类
最新评论

HashMap解决hash冲突的方法

 
阅读更多

原文地址:http://xiaolu123456.iteye.com/blog/1485349

在Java编程语言中,最基本的结构就是两种,一种是数组,一种是模拟指针(引用),所有的数据结构都可以用这两个基本结构构造,HashMap也一样。当程序试图将多个 key-value 放入 HashMap 中时,以如下代码片段为例:

HashMap<String,Object> m=new HashMap<String,Object>(); 
m.put("a", "rrr1"); 
m.put("b", "tt9"); 
m.put("c", "tt8"); 
m.put("d", "g7"); 
m.put("e", "d6"); 
m.put("f", "d4"); 
m.put("g", "d4"); 
m.put("h", "d3"); 
m.put("i", "d2"); 
m.put("j", "d1"); 
m.put("k", "1"); 
m.put("o", "2"); 
m.put("p", "3"); 
m.put("q", "4"); 
m.put("r", "5"); 
m.put("s", "6"); 
m.put("t", "7"); 
m.put("u", "8"); 
m.put("v", "9");
HashMap 采用一种所谓的“Hash 算法”来决定每个元素的存储位置。当程序执行 map.put(String,Obect)方法 时,系统将调用String的 hashCode() 方法得到其 hashCode 值——每个 Java 对象都有 hashCode() 方法,都可通过该方法获得它的 hashCode 值。得到这个对象的 hashCode 值之后,系统会根据该 hashCode 值来决定该元素的存储位置。源码如下:

   public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            //判断当前确定的索引位置是否存在相同hashcode和相同key的元素,如果存在相同的hashcode和相同的key的元素,那么新值覆盖原来的旧值,并返回旧值。
            //如果存在相同的hashcode,那么他们确定的索引位置就相同,这时判断他们的key是否相同,如果不相同,这时就是产生了hash冲突。
            //Hash冲突后,那么HashMap的单个bucket里存储的不是一个 Entry,而是一个 Entry 链。
            //系统只能必须按顺序遍历每个 Entry,直到找到想搜索的 Entry 为止——如果恰好要搜索的 Entry 位于该 Entry 链的最末端(该 Entry 是最早放入该 bucket 中),
            //那系统必须循环到最后才能找到该元素。
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                return oldValue;
            }
        }
        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

上面程序中用到了一个重要的内部接口:Map.Entry,每个 Map.Entry 其实就是一个 key-value 对。从上面程序中可以看出:当系统决定存储 HashMap 中的 key-value 对时,完全没有考虑 Entry 中的 value,仅仅只是根据 key 来计算并决定每个 Entry 的存储位置。这也说明了前面的结论:我们完全可以把 Map 集合中的 value 当成 key 的附属,当系统决定了 key 的存储位置之后,value 随之保存在那里即可.HashMap程序经过我改造,我故意的构造出了hash冲突现象,因为HashMap的初始大小16,但是我在hashmap里面放了超过16个元素,并且我屏蔽了它的resize()方法。不让它去扩容。这时HashMap的底层数组Entry[]table结构如下:

Hashmap里面的bucket出现了单链表的形式,散列表要解决的一个问题就是散列值的冲突问题,通常是两种方法:链表法和开放地址法。链表法就是将相同hash值的对象组织成一个链表放在hash值对应的槽位;开放地址法是通过一个探测算法,当某个槽位已经被占据的情况下继续查找下一个可以使用的槽位。java.util.HashMap采用的链表法的方式,链表是单向链表。形成单链表的核心代码如下:

    void addEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        if (size++ >= threshold)
            resize(2 * table.length);
 }

上面方法的代码很简单,但其中包含了一个设计:系统总是将新添加的 Entry 对象放入 table 数组的 bucketIndex 索引处——如果 bucketIndex 索引处已经有了一个 Entry 对象,那新添加的 Entry 对象指向原有的 Entry 对象(产生一个 Entry 链),如果 bucketIndex 索引处没有 Entry 对象,也就是上面程序代码的 e 变量是 null,也就是新放入的 Entry 对象指向 null,也就是没有产生 Entry 链。

HashMap里面没有出现hash冲突时,没有形成单链表时,hashmap查找元素很快,get()方法能够直接定位到元素,但是出现单链表后,单个bucket 里存储的不是一个 Entry,而是一个 Entry 链,系统只能必须按顺序遍历每个 Entry,直到找到想搜索的 Entry 为止——如果恰好要搜索的 Entry 位于该 Entry 链的最末端(该 Entry 是最早放入该 bucket 中),那系统必须循环到最后才能找到该元素。

当创建 HashMap 时,有一个默认的负载因子(load factor),其默认值为 0.75,这是时间和空间成本上一种折衷:增大负载因子可以减少 Hash 表(就是那个 Entry 数组)所占用的内存空间,但会增加查询数据的时间开销,而查询是最频繁的的操作(HashMap 的 get() 与 put() 方法都要用到查询);减小负载因子会提高数据查询的性能,但会增加 Hash 表所占用的内存空间。



分享到:
评论

相关推荐

    hashmap中hash函数的构造问题

    - **解决冲突的方法**:主要有开放地址法(如线性探测、二次探测)和链地址法(即拉链法)。 #### 三、典型哈希函数构造方法 接下来我们将介绍几种典型的哈希函数构造方法,包括SDBMHash、RSHash、JSHash、PJWHash...

    HashMap-hash原理

    综上所述,`HashMap`中的hash算法设计考虑了多种因素,旨在通过合理的高位扩展与低位扩散策略来提高数据分布的均匀性和减少冲突的可能性。通过以上分析,我们可以更加深入地理解`HashMap`内部的工作机制,这对于理解...

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

    这里我们将详细讨论在HashMap扩容时`rehash`方法中`(e.hash & oldCap) == 0`这一算法的推导。 首先,`e.hash`是HashMap中某个元素的哈希值,它由键对象的`hashCode()`方法计算得出,通常是键对象的哈希码右移16位后...

    05.HashMap相关面试题

    HashMap 使用链表来解决 Hash 冲突问题。 * 在 JDK 1.7 中,HashMap 使用数组+链表来存储键值对,当链表过长时,查询效率非常低。 * 在 JDK 1.8 中,HashMap 使用数组+链表+红黑树来存储键值对,链表过长时,会将其...

    JDK1.8 中 HashMap 如何应对 hash 冲突?.zip

    计算机技术、IT咨询、人工智能AI理论介绍,学习参考资料计算机技术、IT咨询、人工智能AI理论介绍,学习参考资料计算机技术、IT咨询、人工智能AI理论介绍,学习参考资料计算机技术、IT咨询、人工智能AI理论介绍,学习...

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

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

    HashMap总结

    HashMap 使用链表来解决哈希冲突的问题,即当两个键的哈希值相同时,HashMap 使用链表来存储这些键值对。 HashMap 的应用场景 1. 缓存机制:HashMap 可以用来实现缓存机制,例如缓存用户信息、缓存查询结果等。 2....

    Java集合专题总结:HashMap 和 HashTable 源码学习和面试总结

    HashMap是一种基于哈希表的集合类,它的存储结构是一个数组,每个元素是一个单链表的头节点,链表用来解决hash地址冲突问题。HashMap有四个构造方法,其中初始容量和加载因子是影响性能的重要参数。加载因子是哈希表...

    Java中HashMap的工作机制

    如果在计算出的位置上有现成的Entry存在(即发生哈希冲突),HashMap将遍历这个冲突链,检查是否已经存在一个键与新传入的键相等(通过调用equals()方法)。如果存在,它将替换掉旧的值,并返回旧值。如果不存在,它...

    HashMap-master.zip_hash

    标题"HashMap-master.zip_hash"可能指的是一个关于HashMap实现或优化的项目,其中包含了哈希函数的设计和分析。 哈希表的核心思想是通过哈希函数将键(Key)映射到数组的特定位置,使得我们能够以近乎常数的时间...

    HashMap的数据结构

    6. **迭代性能**:由于HashMap使用链表解决哈希碰撞,如果某个哈希桶内的链表过长(例如,出现大量键的哈希码冲突),那么在遍历HashMap时,性能会下降到接近于O(n),其中n是链表的长度。 7. **键的唯一性**:...

    Hash Map for geeks_hashmap_Geeks_源码

    - **哈希冲突**:不同的键可能会产生相同的哈希码,因此HashMap使用链表或红黑树来解决冲突,形成所谓的桶。 - **插入和查找**:插入时,HashMap会根据键的哈希码找到对应的桶,并在桶内使用键的`equals()`方法进行...

    java中HashMap详解.pdf

    键值对存储在Entry对象中,Entry对象包含了键、值以及下一个Entry对象的引用(链表的一部分,用于解决散列冲突)。 当put一个元素时,首先会计算键的hashCode()值,然后通过散列函数找到对应的数组下标。由于不同的...

    用hashmap实现词典查询

    HashMap基于哈希表的概念,它通过计算元素的哈希码(hash code)将键(key)映射到数组的特定位置。当查找某个键时,HashMap会先计算键的哈希码,然后使用这个哈希码找到数组中的相应位置。如果存在冲突(多个键映射...

    自定义map实现java的hashmap

    通过以上分析,我们可以了解到实现一个自定义的HashMap涉及许多细节和技巧,包括哈希函数的设计、冲突解决策略的选择、以及性能优化等。在实际编程中,理解这些概念有助于我们更好地使用和定制HashMap,满足特定需求...

    HashMap介绍和使用

    为了解决这个问题,HashMap提供了自动扩容机制。 **3.1 扩容触发条件** 当HashMap中的元素数量超过容量大小与负载因子的乘积时,HashMap会自动扩容。默认负载因子为0.75,这意味着当HashMap的填充率达到75%时,会...

    易语言HashMap类

    HashMap类基于哈希表(Hash Table)原理,通过计算键的散列值来确定数据在内存中的存储位置,从而实现快速查找。以下是对该类的一些关键知识点的详细解释: 1. **初始设置**:在创建HashMap对象时,通常需要设定...

    HashMap原理.docx

    数组为HashMap提供了基础的存储结构,而链表则用来解决哈希冲突问题,即当多个键值对映射到数组同一位置时的处理机制。在JDK 1.8中,当链表长度达到一定阈值时,还会转换为红黑树以进一步优化性能。 ##### 2.2 哈希...

Global site tag (gtag.js) - Google Analytics