数据结构与算法

3 基本数据结构：哈希表

2020-02-17  本文已影响0人  GoFuncChan

哈希表

什么是哈希表？

哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

哈希函数
index = hashtable(key)

这里的对应关系f称为散列函数，又称为哈希（Hash函数），采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表（Hash table）。

哈希表hashtable(key，value) 就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。（或者：把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，而不可能从散列值来唯一的确定输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。）

而当使用哈希表进行查询的时候，就是再次使用哈希函数将key转换为对应的数组下标，并定位到该空间获取value，如此一来，就可以充分利用到数组的定位性能进行数据定位。

数据结构特点

哈希表基本思想

1.在元素关键字k和元素存储位置p之间建立对应关系f，使得p=f(k)，f称为哈希函数。

2.在创建哈希表时，把关键字为k的元素直接存入地址为f(k)的单元。

3.当查找关键字为k的元素时，利用哈希函数计算出该元素的存储位置p=f(k)，从而达到按关键字直接存取元素的目的。

如果关键字集合很大，则关键字值中不同的元素可能会映像到和哈希表相同的地址上，即k1≠k2。但是H(k1)=H(k2)，上述现象被称为冲突。在这种情况下，通常称k1和k2是同义词。在实际应用中，不能避免上述冲突的情形，只能通过改进哈希函数的性能来减少冲突。

所以构建哈希表的基本思路就两个：

如何构造哈希函数？

在构造哈希函数时需要遵循如下原则：

构造哈希函数的方法有多种，其中最为常用的有如下5种：

1.数字分析法

如果预先知道关键字集合，则当每个关键字的位数比哈希表的地址码位数多时，可以从关键字中选出分布较均匀的若干位来构成哈希地址。假设有80个记录，关键字是一个8位的十进制整数：m1 m2 m3 …m7 m8 ，如哈希表长度取值100，则哈希表的地址空间为：00~99。如果经过分析之后，各关键字中m4 和m7 的取值分布比较均匀，则哈希函数为：h(key)=h(m1 m2 m3 …m7 m8 )=m4 m7 。反之，如果经过分析之后，各关键字中m1 和m8 的取值分布很不均匀，例如m1 都等于5，m8 都等于2，则哈希函数为：h(key)=h(m1 m2 m3 …m7 m8 )=m1 m8 ,这种算法的误差很大，所以不可取。

2.平方取中法

如果无法确定关键字中哪几位分布比较均匀，则可以先求出关键字的平方值，然后按照需要取平方值的中间几位作为哈希地址。因为平方后的中间几位和关键字中的每一位都相关，所以不同的关键字会以较高的概率产生不同的哈希地址。

假设把英文字母在字母表中的位置序号作为该英文字母的内部编码，例如K的内部编码为11，E的内部编码为05，Y的内部编码为25，A的内部编码为01，B的内部编码为02，由此可以得出关键字“KEYA”的内部代码为11052501。同理，也可以得到关键字“KYAB”、“AKEY”、“BKEY”的内部编码。对关键字进行平方运算之后，取出第7位到第9位作为该关键字的哈希地址，如下表：

关键字 内部编码 内部编码的平方值 h(key)关键字的哈希地址
KEYA 11050201 122157778355001 778
KYAB 11250102 126564795010404 795
AKEY 01110525 001233265775625 265
BKEY 02110525 004454315775625 315
3.分段叠加法

分段叠加法是指，按照哈希表地址位数将关键字分成位数相等的几部分，其中最后一部分可以比较短。然后将这几部分相加，舍弃最高进位后的结果就是该关键字的哈希地址。分段叠加有折叠法与移位法两种。移位法是指将分割后的每部分低位对齐相加；折叠法是指从一端向另一端沿分割边界来回折叠，用奇数段表示正序，用偶数段表示倒序，然后将各段相加。

4.除留余数法

为了更加直观地了解除留余数法，在此举一个例子。假设哈希表长为n，p为小于或等于n的最大素数，则哈希函数为：
h（k）=k % p,
其中%为模p的取余运算。

假设待散列元素为（18，75，60，43，54，90，46），表长n=10，p=7，则有：

此时冲突较多，为减少冲突，可以取较大的n值和p值，例如n=p=13，此时结果如下：

6.伪随机数法

伪随机数法是指采用一个伪随机函数当作哈希函数，即h(key)=random(key)。

哈希函数的衡量标准

在实际应用中，读者应根据具体情况而灵活地采用不同的方法，并使用实际数据来测试它的性能，以便做出正确判定。在判断时通常需要考虑如下5个因素：

如何处理冲突？

使用性能良好的哈希函数可以减少冲突，但是通常不可能完全避免冲突，所以解决冲突是哈希法的另一个关键问题。无论是在创建哈希表时，还是在查找哈希表时都会遇到冲突，在这两种情况下解决冲突的方法是一致的。

以创建哈希表为例，有以下4种常用的解决冲突的方法：

1.开放地址法

当关键字key的哈希地址m=H(key)出现冲突时，以m为基础产生另一个哈希地址m1 ，如果m2 还是冲突，再以m为基础产生另一个哈希地址m2 ，…，如此继续，一直到找出一个不冲突的哈希地址mi 为止，此时将相应元素存入其中。

2. 再哈希法

再哈希法能够同时构造多个不同的哈希函数，具体格式如下所示：

Hi=RHi（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，则用链地址法处理冲突的结果如下图所示。


拉链法.png

上组关键字的平均查找长度ASL=(1×7+2×4+3×1)/12=1.5。

4. 建立公共溢出区

建立公共溢出区的基本思想是将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

哈希表的查找过程

哈希表的查找过程与哈希表的创建过程一样。当想查找关键字为K的元素时，首先计算p0=hash(K)，然后根据计算结果进行处理：

1.如果单元p0为空，则不存在所查的元素。

2.如果单元p0中元素的关键字为K，则找到所查元素。

否则重复下述操作来解决冲突过程：按解决冲突的方法，找出下一个哈希地址pi，如果单元pi为空，则不存在所查的元素；如果单元pi中元素的关键字为K，则找到所查元素。

分析哈希法的性能

因为冲突的存在，哈希法仍然需要比较关键字，然后用平均查找长度来评价哈希法的查找性能。在哈希法中，影响关键字比较次数的因素有3个，分别是哈希函数、处理冲突的方法以及哈希表的装填因子。定义哈希表的装填因子α的格式如下：

α=哈希表中的元素个数/哈希表的长度

α能够描述哈希表的装满程度。如果α越小，发生冲突的可能性就越小；如果α越大，则发生冲突的可能性就越大。假设哈希函数是均匀的，则只有两个影响平均查找长度的因素，分别是处理冲突的方法和α。

Go 模拟实现一个哈希表

go自带map结构，这里模拟哈希表的实现原理
常见实现方式：
拉链法：数组+链表+哈希算法+素数生成函数



// 一个数组链表模拟哈希表
type HashMap [16]*node

// 哈希表方法
// 往表里存key值
func (hmap *HashMap) SetKey(k string, v interface{}) {
    // 存k先判断存哪里  这里才使用了散列算法计算
    num := hashFunc(k)
    hmap[num].add(k, v)
}

// 取key值
func (hmap *HashMap) GetKey(k string) interface{} {
    num := hashFunc(k)
    return hmap[num].getKey(k)
}

type kv struct {
    key   string
    value interface{}
}
type node struct {
    data kv
    next *node
}

// 新增数据
func (n *node) add(k string, v interface{}) {
    if n.getKey(k) != nil {
        return
    }

    linkNode := n
    for linkNode.next != nil {
        linkNode = linkNode.next
    }

    // 创建新的尾节点
    newNode := new(node)
    newNode.setKv(k,v)
    linkNode.next = newNode
}

// key value 存放方法
func (n *node) setKv(k string, v interface{}) *node {
    n.data.key = k
    n.data.value = v
    return n
}

func (n *node) getKey(k string) interface{} {
    if n.next == nil {
        return nil
    }
    linkNode := n
    for linkNode.next != nil {
        if linkNode.next.data.key == k {
            return n.next.data.value
        } else {
            linkNode = linkNode.next
        }
    }
    return nil
}

// 初始化头节点
func newNodeHead() *node {
    node := new(node)
    node.next = nil
    return node
}

// 创建初始化HashMap
func NewHashMap() *HashMap {
    hashMaps := new(HashMap)
    for i := 0; i < 16; i++ {
        hashMaps[i] = newNodeHead()
    }
    return hashMaps
}

// 简单的哈希函数计算
func hashFunc(key string) int {
    var index int
    index = int(key[0])
    // 询价累积新的数值
    for k := 0; k < len(key); k++ {
        index *= 1103515245 + int(key[k])
    }
    // 右位移2^27次方  这里可以位移任何数  只要别太大导致直接清空
    index >>= 27
    // 按位&  这里想要求32以内就 32-1即可   也就是说  index跟 1111 进行&  得到15以内的数  跟11111取余则得31以内的数
    index &= 16 - 1

    return index
}
上一篇 下一篇

猜你喜欢

热点阅读