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

By | 03月20日
Advertisement

众所周知,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岁的人口数字统计表,其中,年龄作为关键字,哈希函数取关键字自身,如下表:

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

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

2)平方去中位法:

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

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

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

(2)处理冲突的方法

这里只介绍两种方法:

1)开放定址法

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

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

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

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

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

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

(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 和链地址法处理冲突构造所得的哈希表,如下图所示:

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

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

现在我们来解释下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表介绍参考严蔚敏老师 的《数据结构》

Similar Posts:

  • 详解Oracle多种表连接方式

    详解Oracle多种表连接方式 本文将介绍的是Oracle数据库中的多种表连接方式,包括内连接.外连接.自连接等等.希望对大家有所帮助. 1. 内连接(自然连接) 2. 外连接 (1)左外连接 (左边的表不加限制) (2)右外连接(右边的表不加限制) (3)全外连接(左右两表都不加限制) 3. 自连接(同一张表内的连接) SQL的标准语法: select table1.column,table2.column from table1 [inner | left | right | full ]

  • PE 结构详解4 区块表定义及属性

    这一讲我们结合实例来谈谈区块表的定义以及各个属性的含义. 首先,我们先用之前学过的一点知识在二进制文件中手动翻找区块表,这样做的好处是可以使你很快的对PE结构牢记于心. 学来的东西就是能用的东西,不能用的理论是空谈,是瞎扯. 这里我们经过千辛万苦终于找到了我们的区块表了(当然将来我会教大家写一个自己的工具,让工具去找,现在让大家自己动手是为了增强感觉!),现在我们联系上一章节提到的区块表的结构对各个成员进行详细的分析: typedef struct _IMAGE_SECTION_HEADER {

  • JFinal的validator详解和防止表单重复提交

    JFinal的架构中没有专门的Validator,它的validator就是Interceptor.完全可以把它当成一个普通的Interceptor使用. 例如在save方法上添加@Before({ Tx.class, SkuValidator.class }),表示它将执行Tx.SkuValidator中的public void intercept(Invocation inv) 方法,该方法是Interceptor的接口方法.Validator是抽象类,实现了Interceptor,定义了p

  • PE文件详解之块表

    先来看看PE文件框架结构,多看几遍,就不陌生啦 按照进度,今天该学习块表啦. PE文件到内存的映射. 在执行一个PE文件的时候,Windows并不是在一开始就将整个文件读入内存,而是采用域内存映射文件机制类似的机制. 换而言之,Windows加载器在装载的时候,仅仅是建立好虚拟地址和PE文件之间的映射关系.当且仅当真正执行到某个内存页中的数据时,这个页面才会被从磁盘提交到物理内存,这种机制使文件装入的速度和文件大小没有太大的关系.但是需要注意的是,系统装载可执行文件的方法又不完全等同于内存映射文

  • Unity SteamVR插件详解一:SteamVR_Controller脚本分析+Vive控制器功能开发

    转载出处:http://blog.csdn.net/qq_15309121/article/details/52043842 大家都知道现在基于Unity开发Vive的应用程序都需要用到SteamVR这个插件,接下来的系列会重点分析该插件中和开发相关的功能.首先介绍的是Vive手柄控制器开发的介绍,基本包含了手柄功能开发的所有信息.如有不全欢迎补充讨论.使用时需要注意的点我会用绿色标出了,对整个脚本执行过程不感兴趣的可以着重看一下绿色部分,开发时注意就好了. 关于控制器的相关信息都包含在Stea

  • CSS中属性position位置详解功能讲解与实例分析

    position有五个值:static.relative.absolute.fixed.inherit. static 是默认值.就是按正常的布局流从上到下从左到右布局,平常我们做网页制作时,没有指定 position,也就表示使用 static. relative 没有脱离布局流,此时可以使用 top.right.bottom.left 属性. top 和 bottom 共存时,使用 top 值,忽略 bottom 值: left 和 right 共存时,使用 left 值,忽略 right

  • Linux mdadm 使用详解及RAID 5简单分析

    为磁盘划分分区 如果MD驱动被编译到内核中,当内核调用执行MD驱动时会自动查找分区为FD(Linux raid autodetect)格式的磁盘.所以一般会使用fdisk工具将HD磁盘或者SD磁盘分区,再设置为FD的磁盘. [root@fc5 mdadm-2.6.3]# fdisk /dev/sdkDevice contains neither a valid DOS partition table, nor Sun, SGI or OSF disklabelBuilding a new DOS

  • C 语言详解 之 乘法表的实现

    #include <stdio.h>int main(){ printf("0*0=0/n"); for(int i=1;i<=9;i++) { for(int j=1;j<=i;j++) { printf("%d*%d=%d ",i,j,i*j); } printf("/n"); } return 0;}

  • Monkey工具详解

    摘要 1.monkey工具介绍 2.用法 命令详解 3.测试结果分析 Android开发的过程中有很多很小而且实用 的小工具,在android开发的api文档中可以查看.http://www.androidcommunitydocs.com/tools/index.html 今天我来讲一下最近上手的一款工具---------monkey.Api网站上是这么定义的:Monkey是运行在模拟器或者设备上的能够生成伪随机的用户事件流(比如 点击.触摸或者手势,还有许多系统级别的事件)的程序.你可以用M

  • LR网页细分图中的时间详解

    Web Page Diagnostics: 1)DNS Resolution:浏览器访问一个网站的时候,一般用的是域名,需要dns服务器把这个域名解析为IP,这个过程就是域名解析时间,如果我们在局域网内直接使用IP访问的话,就没有这个时间了. 使用最接近的DNS服务器,解决DNS名称为一个IP地址所需要的时间.DNS查询测量是DNS解析中问题,或DNS服务器问题的一个很好的指标. 2)Connection:服务器建立连接的时间.需要与Web服务器主机指定的URL建立一个初始连接.连接是测量网络问

Tags: