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

╰+攻爆jí腚メ 2022-06-14 05:44 150阅读 0赞

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

这种方法的基本思想是：首先在元素的关键字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所示。

<table> 
 <thead> 
  <tr> 
   <th>关键字</th> 
   <th>内部编码</th> 
   <th>内部编码平方值</th> 
   <th>H(k)关键字的哈希地址</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>KEYA</td> 
   <td>11050201</td> 
   <td>122157778355001</td> 
   <td>778</td> 
  </tr> 
  <tr> 
   <td>KYAB</td> 
   <td>11250102</td> 
   <td>126564795010404</td> 
   <td>795</td> 
  </tr> 
  <tr> 
   <td>AKEY</td> 
   <td>01110525</td> 
   <td>001233265775625</td> 
   <td>265</td> 
  </tr> 
  <tr> 
   <td>BKEY</td> 
   <td>02110525</td> 
   <td>004454315775625</td> 
   <td>315</td> 
  </tr> 
 </tbody> 
</table>

## 3． 分段叠加法 ##

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

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

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

![这里写图片描述][SouthEast]

## 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

此时没有冲突

## 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号单元

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

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

从上述例子可以看出，线性探测再散列容易产生“**二次聚集**”，即在处理同义词的冲突时又导致非同义词的冲突。例如，当表中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，则用链地址法处理冲突的结果：  
![这里写图片描述][SouthEast 1]

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

本例的平均查找长度 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;
        }
    }

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

[SouthEast]: /images/20220614/8887353b204f466b8d034a375c34a39c.png
[SouthEast 1]: /images/20220614/4c225e29fbb04110b46ef9e615675499.png