`

Map冲突

阅读更多

HashMap解决hash冲突的方法    转的(非原创)

博客分类:
 

       在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 值来决定该元素的存储位置。源码如下:

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

       上面程序中用到了一个重要的内部接口: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采用的链表法的方式,链表是单向链表。形成单链表的核心代码如下:

 

Java代码  收藏代码
  1. void addEntry(int hash, K key, V value, int bucketIndex) {  
  2.     Entry<K,V> e = table[bucketIndex];  
  3.     table[bucketIndex] = new Entry<K,V>(hash, key, value, e);  
  4.     if (size++ >= threshold)  
  5.         resize(2 * table.length);  
  6. bsp;  

     上面方法的代码很简单,但其中包含了一个设计:系统总是将新添加的 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 表所占用的内存空间。

 

分享到:
评论

相关推荐

    C++11 unordered_map与map(插入,遍历,Find)效率对比。

    此外,`std::unordered_map`的空间效率通常低于`std::map`,因为哈希表通常需要额外的存储空间来处理冲突。而`std::map`由于是树结构,其空间开销主要来自指针和节点,相对于哈希表,可能占用较少的内存。 在实际...

    Mapkey非常好用的键盘插件

    4. **热键冲突解决**:Mapkey具有智能检测和处理热键冲突的功能,确保用户设定的快捷键在多软件环境中不会产生冲突,保证了操作的连贯性和一致性。 5. **个性化设置**:用户可以根据个人喜好调整Mapkey的界面布局,...

    delphi7的map控件

    然而,哈希冲突可能会影响性能,选择合适的哈希函数和负载因子可以优化性能。 总的来说,Delphi 7的Map控件,通过TDictionary类,为开发人员提供了一种强大且灵活的方式来管理和操作键值对数据,广泛应用于各种数据...

    unordered_map_unordered_map_

    4. 冲突解决:哈希函数可能会导致不同的键映射到相同的桶,因此`unordered_map`还需要一种冲突解决策略。通常使用链地址法,即每个桶内维护一个链表,存放映射到该桶的所有键值对。 在`unordered_map.cpp`文件中,...

    Java Map 按值排序

    (oldValue, newValue) -&gt; oldValue, // 解决键冲突问题 LinkedHashMap::new // 保持排序顺序 )); ``` 这里,我们使用了`comparingByValue()`方法来比较值,并通过`reversed()`使其降序排列。如果需要升序,去掉`...

    java中map集合的用法

    然而,由于哈希冲突,最坏情况下可能退化为O(n)。 **3. TreeMap** TreeMap基于红黑树数据结构,它保持了插入的键的自然排序或自定义比较器的排序。插入和查找的平均时间复杂度为O(logn)。如果键是不可比较的,则会...

    jquery快捷键插件mapkey

    5. **冲突处理**:插件内置冲突检测机制,当快捷键设置有冲突时,可以进行适当的处理,避免影响用户体验。 ### 三、使用步骤 1. **引入jQuery库**:首先确保页面已经引入了jQuery库,可以通过CDN或者本地文件引用...

    Java中的`java.util.stream.Collectors.toMap()`方法有什么作用

    在Java中,java.util.stream.Collectors.toMap()方法是一个非常实用的工具,它允许我们将流(Stream)中的元素收集到一个Map中。这个方法是Collectors类中的一个静态方法,它实现了Collector接口,用于在流的终止...

    uni-app的map层级问题封装.zip

    在uni-app开发中,地图组件(Map)是一个常用的功能,特别是在构建移动应用时,它能够为用户提供导航、定位等服务。然而,在实际开发过程中,开发者可能会遇到地图层级问题,即地图与其他组件重叠或者交互不顺畅的...

    dl_ul_map.rar_802.16_802.16e_DL_MAP_map 协议_map协议

    UL_MAP告诉UE何时开始传输,以及使用哪些频谱资源,以避免上行链路的冲突。 3. MAP协议解析 开发802.16e物理层上下行MAP解析程序是为了理解和解码这些控制信息,从而实现对WiMAX网络的深入监控和分析。程序通过...

    SSH增删改查使用Map容器

    - 键的哈希冲突可能影响性能。 - 键值对的顺序可能不固定,不适合需要保持插入顺序的场景。 总结来说,SSH框架与Map容器的结合使得数据管理更为便捷,尤其是在处理复杂的业务逻辑和数据关系时。然而,合理选择数据...

    hash_map的详解

    ### hash_map详解 #### 0. 为什么需要hash_map? 在软件开发中,经常会遇到需要高效存储和查找键值对(key-value)的情况。例如,在管理人物名称及其相关信息时,我们希望能够快速地添加、查找和更新数据。传统的...

    Java中常用Map测试示例

    `HashMap`允许`null`键和`null`值,但请注意,两个不同的对象如果哈希码相同,可能会导致冲突,这需要通过`equals`方法解决。 接下来,我们讨论`EnumMap`,这是专门为枚举类型设计的`Map`实现。`EnumMap`保证了极高...

    对java中Map集合的讲解

    ### 对Java中Map集合的深入解析 #### 一、Map集合概述 Map是Java集合框架中的一个重要组成部分,它提供了一种存储键值对(key-value pair)数据结构的方式。与List和Set不同,Map并没有直接继承自`Collection`接口,...

    哈希映射 hash map

    此外,`hash_map`的性能还依赖于桶的数量,桶的数量越大,每个桶中元素的平均数量就越少,冲突的可能性也就越小,查找效率越高。在实际使用中,可以通过调整桶的数量来优化性能。 使用`hash_map`的示例代码如下: ...

    智鼎MAP职业性格测试(30min107t)全.pdf

    通过了解员工的性格类型,管理者可以更有效地进行人才匹配、团队组建和冲突解决,进而提升团队的整体工作效率和工作氛围。 知识点十:个人隐私保护 在进行职业性格测试时,个人所填写的信息需要妥善保护。组织方...

    Hash map 哈希表

    哈希表,也被称为Hash Map,是计算机科学中一种高效的数据结构,用于存储键值对。它通过一种称为哈希函数的过程将键映射到数组的特定位置,从而实现快速的查找、插入和删除操作。在哈希表中,查找时间通常接近常数...

    Hash_map 实现源码

    哈希映射(Hash Map)是一种常见的数据结构,它提供了键值对(Key-Value Pair)的快速存储和检索功能。在C++中,STL(Standard Template Library)提供了一个名为`std::unordered_map`的容器,它是基于哈希表实现的...

    小程序仿摩拜单车(解决map层级过高问题)

    合理地配置和布局这两个组件,能有效避免层级冲突。 3. **事件监听和处理**:监听map的事件,比如`markerTap`,当用户点击Marker时,可以弹出相应的信息窗口或者执行其他操作。同时,通过监听用户的操作,动态调整...

    集合Map

    这意味着IdentityHashMap的性能不会受到重写`equals()`和`hashCode()`方法的影响,但在处理大量对象时,由于没有利用对象的逻辑相等性,可能导致哈希冲突增多,进而影响效率。 四、适用场景 IdentityHashMap适合...

Global site tag (gtag.js) - Google Analytics