数据结构 哈希表的原理和代码实现

哈希法又称散列法杂凑法以及关键字地址计算法等,相应的表称为哈希表。

这种方法的基本思想是:首先在元素的关键字k和元素的存储位置p之间建立一个对应关系f,使得p=f(k),f称为哈希函数。创建哈希表时,把关键字为k的元素直接存入地址为f(k)的单元;以后当查找关键字为k的元素时,再利用哈希函数计算出该元素的存储位置p=f(k),从而达到按关键字直接存取元素的目的

当关键字集合很大时,关键字值不同的元素可能会映象到哈希表的同一地址上,即 k1≠k2 ,但 H(k1)=H(k2),这种现象称为冲突,此时称k1和k2为同义词。实际中,冲突是不可避免的,只能通过改进哈希函数的性能来减少冲突。

综上所述,哈希法主要包括以下两方面的内容

  • 1)如何构造哈希函数
  • 2)如何处理冲突。

哈希函数的构造方法

构造哈希函数的原则是:①函数本身便于计算;②计算出来的地址分布均匀,即对任一关键字k,f(k) 对应不同地址的概率相等,目的是尽可能减少冲突。

下面介绍

构造哈希函数常用的五种方法。

1. 数字分析法

如果事先知道关键字集合,并且每个关键字的位数比哈希表的地址码位数多时,可以从关键字中选出分布较均匀的若干位,构成哈希地址。例如,有80个记录,关键字为8位十进制整数d1d2d3…d7d8,如哈希表长取100,则哈希表的地址空间为:00~99。假设经过分析,各关键字中 d4和d7的取值分布较均匀,则哈希函数为:h(key)=h(d1d2d3…d7d8)=d4d7。例如,h(81346532)=43,h(81301367)=06。相反,假设经过分析,各关键字中 d1和d8的取值分布极不均匀, d1 都等于5,d8 都等于2,此时,如果哈希函数为:h(key)=h(d1d2d3…d7d8)=d1d8,则所有关键字的地址码都是52,显然不可取。

2.平方取中法

当无法确定关键字中哪几位分布较均匀时,可以先求出关键字的平方值,然后按需要取平方值的中间几位作为哈希地址。这是因为:平方后中间几位和关键字中每一位都相关,故不同关键字会以较高的概率产生不同的哈希地址。
例:我们把英文字母在字母表中的位置序号作为该英文字母的内部编码。例如K的内部编码为11,E的内部编码为05,Y的内部编码为25,A的内部编码为01, B的内部编码为02。由此组成关键字“KEYA”的内部代码为11052501,同理我们可以得到关键字“KYAB”、“AKEY”、“BKEY”的内部编码。之后对关键字进行平方运算后,取出第7到第9位作为该关键字哈希地址,如图8.23所示。

关键字 内部编码 内部编码平方值 H(k)关键字的哈希地址
KEYA 11050201 122157778355001 778
KYAB 11250102 126564795010404 795
AKEY 01110525 001233265775625 265
BKEY 02110525 004454315775625 315

3. 分段叠加法

这种方法是按哈希表地址位数将关键字分成位数相等的几部分(最后一部分可以较短),然后将这几部分相加,舍弃最高进位后的结果就是该关键字的哈希地址。具体方法有折叠法移位法

  • 移位法是将分割后的每部分低位对齐相加
  • 折叠法是从一端向另一端沿分割界来回折叠(奇数段为正序,偶数段为倒序),然后将各段相加。

例如:key=12360324711202065,哈希表长度为1000,则应把关键字分成3位一段,在此舍去最低的两位65,分别进行移位叠加和折叠叠加,求得哈希地址为105和907,如图8.24所示。

这里写图片描述

4. 除留余数法

假设哈希表长为m,p为小于等于m的最大素数,则哈希函数为h(k)=k % p ,其中%为模p取余运算。

例如,已知待散列元素为(18,75,60,43,54,90,46),表长m=10,p=7,则有

h(18)=18 % 7=4 h(75)=75 % 7=5 h(60)=60 % 7=4
h(43)=43 % 7=1 h(54)=54 % 7=5 h(90)=90 % 7=6
h(46)=46 % 7=4

此时冲突较多。为减少冲突,可取较大的m值和p值,如m=p=13,结果如下:

h(18)=18 % 13=5 h(75)=75 % 13=10 h(60)=60 % 13=8
h(43)=43 % 13=4 h(54)=54 % 13=2 h(90)=90 % 13=12
h(46)=46 % 13=7

此时没有冲突

0 1 2 3 4 5 6 7 8 9 10 11 12
54 43 18 46 60 75 90

5. 伪随机数法

采用一个伪随机函数做哈希函数,即h(key)=random(key)。

在实际应用中,应根据具体情况,灵活采用不同的方法,并用实际数据测试它的性能,以便做出正确判定。通常应考虑以下五个因素 :

  • 计算哈希函数所需时间 (简单)。
  • 关键字的长度。
  • 哈希表大小。
  • 关键字分布情况。
  • 记录查找频率

处理冲突的方法

通过构造性能良好的哈希函数,可以减少冲突,但一般不可能完全避免冲突,因此解决冲突是哈希法的另一个关键问题。创建哈希表和查找哈希表都会遇到冲突,两种情况下解决冲突的方法应该一致。下面以创建哈希表为例,说明解决冲突的方法。常用的解决冲突方法有以下四种:

1. 开放定址法

这种方法也称再散列法,其基本思想是:

当关键字key的哈希地址p=H(key)出现冲突时,以p为基础,产生另一个哈希地址p1,如果p1仍然冲突,**再以p为基础,产生另一个哈希地址**p2,…,直到找出一个不冲突的哈希地址pi ,将相应元素存入其中。这种方法有一个通用的再散列函数形式:

      Hi=(H(key)+di)% m   i=1,2,…,n

其中H(key)为哈希函数,m 为表长,di称为增量序列。增量序列的取值方式不同,相应的再散列方式也不同。主要有以下三种:

线性探测再散列

dii=1,2,3,…,m-1

这种方法的特点是:冲突发生时,顺序查看表中下一单元,直到找出一个空单元或查遍全表。

二次探测再散列

di=12,-12,22,-22,…,k2,-k2 ( k<=m/2 )

这种方法的特点是:冲突发生时,在表的左右进行跳跃式探测,比较灵活。

伪随机探测再散列

di=伪随机数序列。
具体实现时,应建立一个伪随机数发生器,(如i=(i+p) % m),并给定一个随机数做起点。

例子

例如,已知哈希表长度m=11,哈希函数为:H(key)= key % 11,则 H(47)=3,H(26)=4,H(60)=5

假设下一个关键字为69,则H(69)=3,与47冲突。如果用线性探测再散列处理冲突,下一个哈希地址为H1=(3 + 1)% 11 = 4,仍然冲突,再找下一个哈希地址为H2=(3 + 2)% 11 = 5,还是冲突,继续找下一个哈希地址为H3=(3 + 3)% 11 = 6,此时不再冲突,将69填入5号单元

0 1 2 3 4 5 6 7 8 9 10
47 26 60 69

如果用二次探测再散列处理冲突,下一个哈希地址为H1=(3 + 12)% 11 = 4,仍然冲突,再找下一个哈希地址为H2=(3 - 12)% 11 = 2,此时不再冲突,将69填入2号单元

0 1 2 3 4 5 6 7 8 9 10
69 47 26 60

如果用伪随机探测再散列处理冲突,且伪随机数序列为:2,5,9,……..,则下一个哈希地址为H1=(3 + 2)% 11 = 5,仍然冲突,再找下一个哈希地址为H2=(3 + 5)% 11 = 8,此时不再冲突,将69填入8号单元

0 1 2 3 4 5 6 7 8 9 10
47 26 60 69

从上述例子可以看出,线性探测再散列容易产生“二次聚集”,即在处理同义词的冲突时又导致非同义词的冲突。例如,当表中i, i+1 ,i+2三个单元已满时,下一个哈希地址为i, 或i+1 ,或i+2,或i+3的元素,都将填入i+3这同一个单元,而这四个元素并非同义词。

线性探测再散列的优点是:只要哈希表不满,就一定能找到一个不冲突的哈希地址,而二次探测再散列和伪随机探测再散列则不一定。

2.再哈希法

这种方法是同时构造多个不同的哈希函数:

Hi=RH1(key)  i=1,2,…,k

当哈希地址Hi=RH1(key)发生冲突时,再计算Hi=RH2(key)……,直到冲突不再产生。这种方法不易产生聚集,但增加了计算时间。

3. 链地址法

这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表,并将单链表的头指针存在哈希表的第i个单元中,因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。

例如,已知一组关键字(32,40,36,53,16,46,71,27,42,24,49,64),哈希表长度为13,哈希函数为:H(key)= key % 13,则用链地址法处理冲突的结果:
这里写图片描述

查找成功时的平均查找长度=表中每个元素查找成功时的比较次数之和/表中元素个数;

本例的平均查找长度 ASL=(1*7+2*4+3*1)=1.5

这里有一个概念

装填因子=表中的记录数/哈希表的长度

如果装填因子越小,表明表中还有很多的空单元,则发生冲突的可能性越小;而装填因子越大,则发生冲突的可能性就越大,在查找时所耗费的时间就越多。因此,Hash表的平均查找长度和装填因子有关。有相关文献证明当装填因子在0.5左右的时候,Hash的性能能够达到最优。因此,一般情况下,装填因子取经验值0.5。

4、建立公共溢出区

这种方法的基本思想是:将哈希表分为基本表和溢出表两部分,凡是和基本表发生冲突的元素,一律填入溢出表

代码实现

public class Entry<K, V> {

    private K key;
    private V value;
    private int hash;

    private Entry<K, V> next;

    public Entry() {
    }

    public Entry(K key, V value,int hash) {
        this.key = key;
        this.value = value;
        this.hash = hash;
    }

    public int getHash() {
        return hash;
    }

    public void setHash(int hash) {
        this.hash = hash;
    }

    public K getKey() {
        return key;
    }

    public void setKey(K key) {
        this.key = key;
    }

    public V getValue() {
        return value;
    }

    public void setValue(V value) {
        this.value = value;
    }

    public Entry<K, V> getNext() {
        return next;
    }

    public void setNext(Entry<K, V> next) {
        this.next = next;
    }
}
public class HashMap<K, V> {

    /**
     * 默认容量
     */
    private static final int DEFAULT_CAPACITY = 16;
    /**
     * 装填因子
     */
    private static double LOAD_FACTOR = 0.75;

    /**
     * 实际存储的数组
     */
    private Entry<K, V>[] container;

    /**
     * 当前容量
     */
    private int size;//
    /**
     * 可以存储最大的数
     */
    private int max;

    @SuppressWarnings("unchecked")
    public HashMap() {
        this(DEFAULT_CAPACITY, LOAD_FACTOR);
    }

    @SuppressWarnings("unchecked")
    public HashMap(int capacity, double factor) {
        LOAD_FACTOR = factor;
        max = (int) (LOAD_FACTOR * capacity);
        container = new Entry[(int) (capacity * factor)];
    }

    /**
     * 存数据
     *
     * @param key   键
     * @param value 值
     */
    public boolean put(K key, V value) {
        int hash = key.hashCode();
        Entry<K, V> entry = new Entry<K, V>(key, value, hash);
        if (setEntry(entry, container)) {
            size++;
            return true;
        }
        return false;
    }

    /**
     * 往数组内添加数据
     */
    private boolean setEntry(Entry<K, V> entry, Entry<K, V>[] container) {
        //根据hash找到下表
        int index = indexFor(entry.getHash(), container.length);
        Entry<K, V> temp = container[index];
        if (temp != null) {
            while (temp != null) {
                //如果已经存在 则返回
                if ((temp.getKey() == entry.getKey() || temp.getKey().equals(entry.getKey()))
                        && (temp.getHash() == entry.getHash())
                        && (temp.getValue() == entry.getValue() || temp.getValue().equals(entry.getValue()))) {
                    return false;
                } else{
                    //到达队尾 中断遍历
                    if (temp.getNext() == null) {
                        break;
                    }
                    // 没有到达队尾,继续遍历下一个元素
                    temp = temp.getNext();
                }
            }
            addEntry2Last(temp, entry);
        }
        // 4.若不存在,直接设置初始化元素
        setFirstEntry(entry, index, container);
        return true;
    }

    /**
     * 添加到链表头部
     */
    private void setFirstEntry(Entry<K, V> entry, int index, Entry<K, V>[] container) {
        if (size > max) {
            reSize(container.length * 4);
        }
        container[index] = entry;
        entry.setNext(null);
    }

    /**
     * 根据键查询值
     */
    public V get(K key) {
        //2.计算数组下标
        int index = indexFor(key.hashCode(), container.length);
        //3.根据下标找到元素
        Entry<K, V> entry = container[index];
        //4.如果元素为空 则返回null
        if (entry == null) {
            return null;
        }
        //5.否则遍历链表找到值为key的元素
        while (entry != null) {
            if ((entry.getKey() == key) && (entry.getKey().equals(key))) {
                return entry.getValue();
            }
            entry = entry.getNext();
        }
        //6.未找到返回null
        return null;
    }

    /**
     * 把元素添加到队尾
     */
    private void addEntry2Last(Entry<K, V> temp, Entry<K, V> entry) {
        if (size > max) {
            reSize(container.length * 4);
        }
        temp.setNext(entry);
    }

    /**
     * 根据hashcode映射下标
     */
    private int indexFor(int i, int length) {
        return i & (length - 1);
    }

    /**
     * 数组扩容
     */

    private void reSize(int newSize) {
        @SuppressWarnings("unchecked")
        Entry<K, V>[] newTable = new Entry[newSize];
        max = (int) (newSize * LOAD_FACTOR);
        for (int j = 0; j < container.length; j++) {
            Entry<K, V> entry = container[j];
            while (entry != null) {
                setEntry(entry, newTable);
                entry = entry.getNext();
            }
        }
        container = newTable;
    }
}

版权声明:本文为Thousa_Ho原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Thousa_Ho/article/details/73065017

智能推荐

spring与redis整合和序列化问题

spring与redis整合 首先用docker下载redis 下载:docker pull redis 运行:docker run -d -p 6379:6379 --name myredis docker.io/redis 连接redis Desktop Manager 然后开始在springboot上开始配置 application.yml: 自动配置好StringRedisTemplate...

CentOS 7配置南大docker镜像

文章目录 CentOS 7配置南大docker镜像 0.帮助页面 1.系统要求 2.卸载旧版本(没有旧版本可跳过) 3.安装方式 4.准备工作 5.可选操作 Stable Test Nightly 6.安装docker引擎 7. (可选)修改配置文件防止与xshell连接冲突 8.启动docker CentOS 7配置南大docker镜像 0.帮助页面 南大docker源:https://mirr...

Qcon演讲纪实:详解如何在实时视频通话中实现AR功能

2018年4月20日-22日,由 infoQ 主办的 Qcon 2018全球软件开发大会在北京如期举行。声网首席 iOS 研发工程师,iOS 端移动应用产品设计和技术架构负责人龚宇华,受邀分享了《基于 ARkit 和 ARcore,在实时视频通话中实现 AR 功能》,在演讲中剖析了 AR 与 VR 差异,ARKit 的工作原理,以及逐步讲解如何基于 ARKit 与声网Agora SDK 创建 AR...

POJ2348 UVa10368 HDU1525 Euclid's Game【博弈】

Euclid's GameTime Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 4106    Accepted Submission(s): 1947 Probl...

使用Breeze.js编写更好的查询

这篇文章是由同行评审Agbonghama柯林斯 。 感谢所有SitePoint的审稿作出SitePoint内容也可以是最好的! 数据量正在迅速发展,他们正在变得越来越复杂,维护。 许多开发人员希望避免由数据问题他们的工作过程中造成的问题和头痛。 一个使我们的工作更轻松的图书馆是Breeze.js 。 在这篇文章中,我们将讨论我们如何能够写出更好的查询与Breeze.js。 但是首先,我们应该知道什...

猜你喜欢

Netty框架构建Nio编程

~~~ 随手点赞,养成习惯 ~~~ 为什么选择Netty框架 Netty是业界最流行的NIO框架之一,它的健壮性、功能、性能、可定制性和可扩展性在同类框架中都是首屈一指的。 优点: ① API使用简单,开发门槛低 ②功能强大,预置了多种编解码功能,支持多种主流协议 ③ 定制能力强,可以通过ChannelHandler对通信框架进行灵活地扩展; ④性能高,通过与其他业界主流的NIO框架对比,Nett...

【JZOJ5262】【GDOI2018模拟8.12】树(DP,性质题)

Description Solution 首先我们可以知道两个性质:1、路径u-v和路径v-w可以合并为路径u-w;2、路径u1-v1加路径u2-v2和路径u1-v2加路径u2-v1是等价的(就是起始点和终点可以互换) 那么知道这些性质之后就很好做了。我们只用知道每个点多少次做起点和多少次做终点。 我们设f[i]表示满足i子树的需求i上的值要是多少。 那么枚举i的所有儿子,判断a[i]-f[i],...

【String-easy】541. Reverse String II 反转的元素,有反转个数和间隔

1. 题目原址 https://leetcode.com/problems/reverse-string-ii/ 2. 题目描述 3. 题目大意 给定一个字符串,和字符串的间隔k, 这个k表示每k个数反转一次,然后再间隔k个元素再反转k个元素。 4. 解题思路 只要按照间隔去反转就可以了。然后间隔k个元素不反转是通过让i每次递增 2*k完成的。 5. AC代码 6. 相似题型 【1】344. Re...

【C语言笔记结构体】

我们都知道C语言中变量的类型决定了变量存储占用的空间。当我们要使用一个变量保存年龄时可以将其声明为int类型,当我们要使用一个变量保存某一科目的考试成绩时可以将其声明为float。 那么,当我们要做一个学生信息管理系统时,需要保存学生的姓名、学号、年龄等信息,该怎么做呢? 如当要保存三个学生的信息时, 方法一是: 方法二是: 显然,方法二跟更清晰,因为它把name、num、age都集成在一个模板,...

39. Combination Sum 回溯算法简析

LeetCode传送门     这道题要求给你一组正数 C,然后给你一个目标数 T,让你从那组C中找到加在一起等于 T 的那些组合。     例如:给你 [2,3,6,7] 和 7,则返回 [[2,2,3],[7] ] 。      想解决这个问题前,我们首先引入一个新问题,图(树)的遍历问题。  ...