`
茴香豆
  • 浏览: 132380 次
  • 性别: Icon_minigender_2
  • 来自: 桂林
社区版块
存档分类
最新评论

详解哈希表及分析HashMap的实现

阅读更多

         众所周知,HashMap是基于has表实现是的Map。那么,现在,我们首先来分析下什么交hash表。

         1.首先我们来看下哈希表的作用以及它的基本概念

         我们平时查找数据可能会用到折半查找、二叉排序树查找‘或者是B-树查找,在查找数据时进行=、>、<的比较,所以查找的效率会依赖于查找过程中进行的比较次数。

         我们理想的情况是不经过任何比较,一次存取便能得到所查记录。这就要在记录的储存位置和它的关键字之间建立一个确定的对应关系f,使每个关键字和结构中一个惟一的存储位置相对应。这个对应关系我们就称之为哈希函数,根据关键字key和f找到数据的存储位置。对于不同的关键字,可能经过哈希函数的映射后会得到同一个值,即key1!=key2 , f(key1)= f(key2) ,这就得不到惟一的存储位置了。对于这种情况,我们称之为冲突。在一般情况下冲突只能尽可能的少,而不能完全避免。

         对于哈希表来说,还有一个中重要的概念,即哈希表的填充因子:a=表中填入的记录数/哈希表的长度。a标志哈希表的装满程度。直观的看,a越小,发生冲突的可能就越小;反之,a越大,表中已经填入的记录越多,要再填入数据时,发生冲突的可能性就越大,则查找时,给定值需要与之进行比较的关键字的个数也就也多。

         2。哈希表的构造

              对于哈希表来说,它主要由三部分构成:哈希函数、哈希表、冲突处理

             (1)哈希函数的构造方法:

                    1)直接定址法

                          取关键字或关键字的某个线性函数值为哈希地址。即:

                          H(key)=key或H(key)a*key+b

                          其中a和b为常数

                          例如:有一个从1岁到100岁的人口数字统计表,其中,年龄作为关键字,哈希函数取关键字自身,如下表:

                               

 

            由于直接定址所得地址集合和关键字集合的大小相同,因此,对于不同的关键字不会发生冲突。但是,实际中使用这种方法的情况很少,因为随着关键字的增多,哈希表会变得很庞大。

                    2)平方去中位法:

                         取关键字平方后的中间几位为哈希地址。取的位数由表长决定。例子:

                                           

                  3)还有折叠法、数字分析法、除留余数法、随机数法等

              (2)处理冲突的方法

                      这里只介绍两种方法:

                       1)开放定址法

                            

                          其中i=1,2,3。。。。,k(k<=m-1),H(key)为哈希函数,m为哈希表表长,di为增量序列,可能有下列三种情况:di=1,2,3....,m-1,称线性探测在散列;(2)

称二次探测再散列;(3)di=伪随机数序列,称伪随机探测再散列。

                          例如,在长度为11的哈希表中已填有关键字分别为17,60,29的记录,(哈希函数H(key)=key MOD 11),现在有第四个记录,其关键字为38,由哈希函数得到哈希地址为5,产生冲突。若用线性探测再散列的方法处理,得到下个地址是6,仍冲突,再求下个地址7,仍冲突,直到哈希地址为8的 位置为“空”时止,处理冲突的过程结束,记录填入哈希表中序号为8的位置。若用二次探测再散列,则应该填入序号为4的位置。类似的可以得到伪随机再散列的地址。如下图

                      

            (a)插入前(b)线性探测再散列(c)二次探测再散列(d)伪随机探测再散列,伪随机数是9

 

                    2)链地址法

                         将所有关键字为同义词的记录存储在同一线性表中。假设某哈希函数产生的哈希地址在区间[0,m-1]上,则设立一个指针型向量

                           Chain Chain Hash[m];

其每个分量的初始状态都是空指针。凡是哈希地址为i的记录都插入到头指针为ChainHash[i]的链表中。在列表中的插入位置可以在表头或表尾;也可以在中间,以保持同义词在同一线性表中按关键字有序。

                       例如:已知一组关键字为(19,14,23,01,68,20,84,27,55,11,10,79),则按哈希函数H(key)=key MOD 13 和链地址法处理冲突构造所得的哈希表,如下图所示:

                           

———————————————————————————————————————————————————————————

 

现在我们来解释下java是如何实现HashMap的

1.HashMap的哈希函数:

    

  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);
    }
 
 

 经过该函数得到哈希地址,其中&是对二进制的与运算

 

2.HashMap是用链地址法法来处理冲突

 

 

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;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }
 

    

   这段代码是把一对映射数据存入HashMap中,如果存入的数据的键值存在,就返回键对应的值;如果不存在,就进行

  addEntry(hash, key, value, i);操作,并且返回null,表示该数据还未在HashMap中。

  值得说明下,输入的KEY是一个类型如何变成整形数据呢,这里的关键在: int hash = hash(key.hashCode());

  hashCode是超类Object的方法,它能取到对象的内部地址并转换成一个整数。

其中addEntry(hash, key, value, i)为:

 

  

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<K,V>(hash, key, value, e);的代码为:

 

 static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        final int hash;

        /**
         * Creates new entry.
         */
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }
 

   由此我们可以看出,经过哈希函数映射后发生冲突的数据会存在Entry的列表中。

3.HashMap的哈希表

   

transient Entry[] table;
 

   table就是我们上面提到的初始状态都是空指针的表,它的大小为:

 

  static final int MAXIMUM_CAPACITY = 1 <<    30;
  

4.装载因子

 

  static final float DEFAULT_LOAD_FACTOR = 0.75f;
 

   当装入table的数据超出上限(与装载因子有关),则要重构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);
    }
    

    --------------------------------------------------------------------------------------------------------------------

   上述为对hash表的简单介绍以及HashMap的实现过程。

 

   对hash表介绍参考严蔚敏老师 的《数据结构》

 

  • 大小: 2.3 KB
  • 大小: 2.4 KB
  • 大小: 585 Bytes
  • 大小: 853 Bytes
  • 大小: 10.3 KB
  • 大小: 5.3 KB
分享到:
评论
2 楼 Wuaner 2012-09-16  
谢谢分析!
1 楼 greatwqs 2011-12-17  
非常好的解释
 
HashMap map = new HashMap(17,1f)

相关推荐

    彻底搞定哈希表,详解哈希表

    哈希表的应用广泛,例如在编程语言中的HashMap、HashTable等容器,数据库的索引系统,缓存系统等。它们通常具有常数时间复杂度的平均性能,但最坏情况下可能退化为线性时间复杂度,这取决于散列函数的质量和冲突解决...

    Hash(哈希)表详解示例

    文件"哈希表1029"可能是对哈希表的一个具体实现或者一个相关的案例分析。由于没有详细内容,我们无法深入讨论,但可以推测这可能包含了哈希表的创建、插入、查找和冲突解决等基本操作的代码示例,或者是针对特定场景...

    哈希表(HashTable)C++实现.docx

    ### 哈希表(HashTable)C++实现详解 #### 一、引言 哈希表是一种非常重要的数据结构,在实际应用中极为广泛。它通过将键映射到表的一个位置来加速查找记录的速度,这一映射过程称为哈希化。在C++中,标准模板库...

    hashmap面试题_hashmap_

    HashMap是一个基于哈希表实现的键值对存储结构,它提供了快速的插入、删除和查找操作,平均时间复杂度为O(1)。HashMap非线程安全,适合于单线程环境或已经通过并发工具类控制并发的场景。 二、HashMap底层原理 ...

    java中HashMap详解

    HashMap内部基于哈希表(Hash Table)实现,利用哈希函数将键映射到一个特定的位置,以便快速查找和插入元素。以下是HashMap的详细解析: 1. **哈希表的定义**: 哈希表,又称散列表,是一种数据结构,通过哈希...

    Java中HashMap详解(通俗易懂).doc

    HashMap基于哈希表(也称为散列表)原理工作,它允许用户通过键(Key)快速查找对应的值(Value)。在HashMap中,键和值可以是任何类型的对象,只要它们实现了equals()和hashCode()方法,这两个方法用于确定对象的...

    hashMap具体详解

    哈希映射(HashMap)是Java编程语言中一个非常重要的数据结构,主要用于存储键值对。HashMap类位于java.util包中,它实现了Map接口,提供了快速的存取速度,平均时间复杂度为O(1)。这个数据结构的核心原理是哈希函数...

    java中HashMap详解.pdf

    在Java编程语言中,HashMap是基于哈希表实现的数据结构,它是Map接口的一个具体实现,提供了高效的插入、删除和查找操作。HashMap不保证元素的顺序,允许null键和null值。HashMap的工作原理主要依赖于哈希算法,通过...

    详解Java HashMap实现原理

    HashMap是基于哈希表的实现,遵循Map接口,提供键值对的存储功能。以下是对HashMap实现原理的详细解析。 首先,HashMap内部使用了一个瞬时变量数组`table`(也称为“桶”)来存储键值对。桶是一个Entry对象数组,它...

    java中哈希表及其应用详解

    此外,Java还提供了`HashMap`类,它是`Hashtable`的一个替代,虽然两者都实现了哈希表,但`HashMap`是非同步的,更适合多线程环境下的性能需求。而`Hashtable`是线程安全的,适用于需要同步访问的场景。 总的来说,...

    Jdk1.8 HashMap实现原理详细介绍

    首先,HashMap是一个基于哈希表的数据结构,它实现了Map接口。它不保证映射的顺序,并且是非同步的。这意味着在多线程环境中,如果不进行同步控制,可能会出现并发问题。HashMap的核心数据结构是一个Node数组,每个...

    HashMap介绍和使用

    ### HashMap介绍和使用详解 #### 一、HashMap的数据结构 HashMap是Java集合框架的一个重要组成部分,它实现了Map接口,能够存储键值对映射。在Java编程语言中,最基本的数据结构有两种:数组和引用(模拟指针)。...

    马士兵老师HashMap学习笔记

    HashMap是Java编程语言中常用的一种数据结构,它提供了键值对(key-value pair)的存储功能,是基于哈希表实现的。马士兵老师的HashMap学习笔记深入剖析了这一核心组件的工作原理,旨在帮助开发者更深入地理解其内部...

    HashMap-hash原理

    为了实现高效的数据存取操作,`HashMap`内部采用了数组加链表(JDK 1.8以前)或数组加链表/红黑树(JDK 1.8及以后版本)的数据结构。本文将重点解析`HashMap`中hash算法的核心原理及其优化细节。 #### 二、计算Key...

    Java实现简易HashMap功能详解

    Java实现简易HashMap详解 ...Java实现简易HashMap功能详解是一种基于哈希表的数据结构,通过结合实例形式详细分析了Java实现HashMap功能相关原理、操作步骤与注意事项,为开发者提供了一种简洁高效的存储键值对的方法。

    c_hashmap-master_hashmap.keys_C-C++_establishgkb_TheKeys_

    《C语言实现的哈希映射——c_hashmap-master中的keys操作详解》 在计算机科学领域,哈希映射(Hash Map)是一种高效的数据结构,它通过特定的哈希函数将键(Key)映射到数组的索引位置,从而实现快速的查找、插入和...

    HashMap排序

    然而,由于`HashMap`是基于哈希表实现的,所以它并不能保证元素的顺序。这就意味着如果需要按照某种特定顺序来处理`HashMap`中的元素时,就需要采取其他方式来实现排序功能。 #### 一、通过`Comparator`进行排序 ...

    Java 中的HashMap详解和使用示例_动力节点Java学院整理

    HashMap基于哈希表的数据结构实现,具有快速查找、插入和删除的特点。本文将详细介绍HashMap的基本概念、构造函数、数据结构以及源码解析。 ### 1. HashMap简介 HashMap是一个散列表,它通过哈希函数将键映射到...

Global site tag (gtag.js) - Google Analytics