数据结构之哈希表HashTable实例讲解

╰+哭是因爲堅強的太久メ 2022-05-23 09:21 195阅读 0赞

哈希表 是一种以关联方式存储数据的数据结构，在哈希表中，数据以数组格式存储，其中每个数据值都有自己唯一的索引。如果我们知道所需数据的索引，那么数据的访问就会变得非常快。 所以关键是 找到索引， 而检索 数值关键字 到 索引 的方式就是 哈希（Hashing）。

因此，在这个结构中插入和搜索操作非常快，不管数据的大小。哈希表使用数组作为存储介质，并使用散列技术（就是我们的哈希算法）生成一个索引。

### 哈希(Hashing) ###

哈希是一种将一系列键值转换成数组的一系列索引的技术。我们以取模运算（基数是20）来演示哈希算法。  
![这里写图片描述][70]

**图解： 通过hash算法将左边的key映射到右边的存储数组中的索引值。**

假定有以下值键组：注意：第二个值表示key，一般我们(是key,value)才是规范的写法。

(100, 1)  
(100, 2)  
(100, 42)  
key分别为： 1， 2， 42； 使用哈希算法（取模，基数为20）后， 各自映射的索引值应该是： 1， 2， 2。如图：

![这里写图片描述][70 1]

### 哈希碰撞 ###

哈希碰撞：就是不同key的哈希值是一样的。我们的实例：1，2，42 进行 20 取模后，就发生了哈希碰撞，其中2 和 42 哈希后的索引值是一样的。

### 线性推测(Linear Probing) ###

发生哈希碰撞后，我们可以使用简单的线性推测，依次往下寻找直到找到一个空的位置。像42，先哈希再进行线性推测后，索引值为3。因为索引2后面的索引位置3是空的坑位。

![这里写图片描述][70 2]

#### 数据项 ####

class DataItem{ 
            int data;
            int key; //key关键字，对其使用哈希算法
    }

#### 插入数据到hash存储结构中 ####

/** * 插入新值到hash表 * <pre> * hash后，发现坑位没有被占，则占有该坑位； * hash后，发现该坑位被占了： * Step1: key和新插入的key不登，则使用线性推测方式，按队列顺序往后打探下一个坑位的情况（这是一个循环表顺序） * Step2： 循环打探坑位：发现新坑位则占住 * </pre> * @param item */
        static void insert(DataItem item) {
            boolean standFlag = false;
            //获取hash索引
            int idx = hashCode(item.key);
    
            if( null != hashArray[idx]  ) {
    
                if( hashArray[idx].key != item.key ) {
    
                    //【被占】---》 则使用线性推测方式处理，找到空位进入
                    while( null != hashArray[idx] && hashArray[idx].key != item.key ) {
    
                        idx = hashCode( ++idx );
                        if( null == hashArray[idx] ) {
                            hashArray[idx] = item;
                            standFlag = true;
                        }
                    }
                }
    
    
            }else {
                //hash索引处为empty，则坑可用，直接存储
                hashArray[idx] = item;
                standFlag = true;
            }
    
            if( !standFlag ) {
                System.err.println("插入失败！");
            }
        }

#### 检索 ####

/** * 发生hash冲突时，检索效率就会低了，所以hash算法很关键，唯一的最好 * @param key * @return */
        static DataItem search(int key) {
            int idx = hashCode(key);
    
            while(null != hashArray[idx]) {
                //如果存在了哈希冲突（即哈希值已经被占用了）
    
                if(hashArray[idx].key == key) {
                    //如果hash相同的索引key值一样则检索到了
                    return hashArray[idx];
                }
    
                //hash冲突，没有检索到，则线性推测查找
                idx++;
    
                //环绕检索,下一个索引位置
                idx = hashCode(idx);
            }
    
            return null;
        }

#### 完整的哈希检索、插入程序示例 ####

package org.byron4j.dsaa;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.Collections;
    
    /** * hash 表数据结构实例详解 * <pre> * 在哈希表中，数据以数组格式存储，其中每个数据值都有自己唯一的索引 * 哈希是一种将一系列键值转换成数组的一系列索引的技术 * </pre> * @author BYRON.Y.Y * */
    public class HashTableExample { 
    
        private static int SIZE = 20;
    
        private static DataItem[] hashArray = new DataItem[20];
    
        public static void main(String[] args) {
            System.out.println(Arrays.asList(hashArray));
    
    
            /*insert(new DataItem(100, 1)); insert(new DataItem(100, 2)); insert(new DataItem(100, 42)); insert(new DataItem(100, 62)); insert(new DataItem(100, 82)); insert(new DataItem(100, 102)); insert(new DataItem(100, 122)); insert(new DataItem(100, 142));*/
    
            //打乱顺序测试hash
            insert(new DataItem(100, 1));
            insert(new DataItem(100, 2));
            insert(new DataItem(100, 102));
            insert(new DataItem(100, 122));
            insert(new DataItem(100, 42));
            insert(new DataItem(100, 82));
            insert(new DataItem(100, 62));
            insert(new DataItem(100, 142));
    
            insert(new DataItem(100, 162));
            insert(new DataItem(100, 182));
            insert(new DataItem(100, 202));
            insert(new DataItem(100, 222));
            insert(new DataItem(100, 242));
            insert(new DataItem(100, 282));
            insert(new DataItem(100, 262));
            insert(new DataItem(100, 302));
    
            insert(new DataItem(100,322));
            insert(new DataItem(100, 342));
            insert(new DataItem(100,362));
            insert(new DataItem(100, 382));
    
            System.out.println(Arrays.asList(hashArray));
        }
    
    
    
        static class DataItem{
            int data;
            int key;
            public DataItem(int data, int key) {
                super();
                this.data = data;
                this.key = key;
            }
            @Override
            public String toString() {
                return "DataItem [key=" + key + "]";
            }
    
        }
    
        /**简易Hash方法，取模*/
        static int hashCode(int key){
               return key % SIZE;
        }
    
        /** * 发生hash冲突时，检索效率就会低了，所以hash算法很关键，唯一的最好 * @param key * @return */
        static DataItem search(int key) {
            int idx = hashCode(key);
    
            while(null != hashArray[idx]) {
                //如果存在了哈希冲突（即哈希值已经被占用了）
    
                if(hashArray[idx].key == key) {
                    //如果hash相同的索引key值一样则检索到了
                    return hashArray[idx];
                }
    
                //hash冲突，没有检索到，则线性推测查找
                idx++;
    
                //环绕检索,下一个索引位置
                idx = hashCode(idx);
            }
    
            return null;
        }
    
    
        /** * 插入新值到hash表 * <pre> * hash后，发现坑位没有被占，则占有该坑位； * hash后，发现该坑位被占了： * Step1: key和新插入的key不等，则使用线性推测方式，按队列顺序往后打探下一个坑位的情况（这是一个循环表顺序） * Step2： 循环打探坑位：发现新坑位则占住 * </pre> * @param item */
        static void insert(DataItem item) {
            boolean standFlag = false;
            //获取hash索引
            int idx = hashCode(item.key);
    
            if( null != hashArray[idx]  ) {
                if( hashArray[idx].key != item.key ) {
                    //【被占】---》 则使用线性推测方式处理，找到空位进入
                    while( null != hashArray[idx] && hashArray[idx].key != item.key ) {
    
                        idx = hashCode( ++idx );
                        if( null == hashArray[idx] ) {
                            hashArray[idx] = item;
                            standFlag = true;
                        }
                    }
                }
    
    
            }else {
                //hash索引处为empty，则坑可用，直接存储
                hashArray[idx] = item;
                standFlag = true;
            }
    
            if( !standFlag ) {
                System.err.println("插入失败！");
            }
        }
    }

运行结果如下：

[null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null]
    
    
    [DataItem [key=382], DataItem [key=1], DataItem [key=2], DataItem [key=102], DataItem [key=122], DataItem [key=42], DataItem [key=82], DataItem [key=62], DataItem [key=142], DataItem [key=162], DataItem [key=182], DataItem [key=202], DataItem [key=222], DataItem [key=242], DataItem [key=282], DataItem [key=262], DataItem [key=302], DataItem [key=322], DataItem [key=342], DataItem [key=362]]

[70]: /images/20220523/73221642bf574760a423a5932f6e3131.png
[70 1]: /images/20220523/e89529501a9c427897a791b7821b638b.png
[70 2]: /images/20220523/94349e8f905d44dd860a1b2c8692c9ea.png