Hash算法的设计原理与代码实现

朴灿烈づ我的快乐病毒、 2022-11-05 11:48 169阅读 0赞

# 一：Hash算法的设计原理 #

## 1：构建hash函数的原则是： ##

*  函数本身便于计算
 *  计算出来的地址分布均匀，即对任一关键字K，H(K)对应不同地址的概率相等，目的是尽可能减少冲突。

## 2：构建Hash函数常用的方法 ##

*  除留余数法

假如哈希表的长为m，p为小于等于m的最大素数，则哈希函数为H(K)=K%p，其中%为模P取余运算

*  伪随机数法

采用一个伪随机函数作哈希函数，即H(key)=random(key)

# 二：处理Hash冲突的方法 #

*  再哈希法

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

![Hi = RHi(key), i =1,2,...,k][Hi _ RHi_key_ i _1_2_..._k]

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

*  链地址法

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

*  建立公共溢出区

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

# 二：Hash代码的实现 #

Employee实体类：

package com.test;
    
    /**
     * @author lizhangyu
     * @date 2021/3/6 12:23
     */
    public class Employee {
    
        public int id;
        public String name;
        public Employee next;
    
        public Employee(int id, String name) {
            this.id = id;
            this.name = name;
        }
    }

EmpLinkedList实体类

package com.test;
    
    /**
     * @author lizhangyu
     * @date 2021/3/6 12:26
     */
    public class EmpLinkedList {
    
        private Employee head;
    
        /**
         * 添加
         * @param employee
         */
        public void add(Employee employee) {
            if (head == null) {
                head = employee;
                return;
            }
    
            Employee cur = head;
    
            while (true) {
                if (cur.next == null) {
                    break;
                }
                cur = cur.next;
            }
    
            cur.next = employee;
        }
    
        /**
         * 遍历链表
         * @param no
         */
        public void list(int no) {
            if (head == null) {
                System.out.println("第" + (no + 1) + "条链表为空" );
                return;
            }
            System.out.print("第" + (no + 1) + "条链表信息为");
            Employee cur = head;
            while(true) {
                System.out.printf("=> id=%d name=%s\t",cur.id, cur.name);
                if (cur.next == null) {
                    break;
                }
                cur = cur.next;
            }
            System.out.println();
        }
    
        /**
         * 查找
         * @param id
         * @return
         */
        public Employee find(int id) {
            if (head == null) {
                System.out.println("链表为空");
                return null;
            }
    
            Employee cur = head;
    
            while (true) {
                if (cur.id == id) {
                    break;
                }
    
                if (cur.next == null) {
                    cur = null;
                    break;
                }
    
                cur = cur.next;
            }
    
            return cur;
        }
    
    }

HashTable实体类：

package com.test;
    
    /**
     * @author lizhangyu
     * @date 2021/3/6 12:06
     */
    public class HashTable {
    
        private int size;
        private EmpLinkedList[] empLinkedListArray;
    
        public HashTable(int size) {
            this.size = size;
            this.empLinkedListArray = new EmpLinkedList[size];
            //初始化链表
            for (int i = 0; i < size ; i++) {
                empLinkedListArray[i] = new EmpLinkedList();
            }
        }
    
        /**
         * 查找
         * @param id
         */
        public void find(int id) {
            int empLinkedListNO = hashFun(id);
            Employee employee = empLinkedListArray[empLinkedListNO].find(id);
            if (employee != null) {
                System.out.printf("在第%d条链表中找到雇员id = %d\n", (empLinkedListNO + 1), id);
            }else {
                System.out.println("在哈希表中中找到雇员");
            }
        }
    
        /**
         * 遍历
         */
        public void list() {
            for (int i = 0; i < size; i++) {
                empLinkedListArray[i].list(i);
            }
        }
    
        /**
         * 添加
         * @param employee
         */
        public void add(Employee employee) {
            int employeeNo = hashFun(employee.id);
            empLinkedListArray[employeeNo].add(employee);
        }
    
        /**
         * 取模运算
         * @param id
         * @return
         */
        public int hashFun(int id) {
            return id % size;
        }
    }

HashTableDemo测试类

package com.test;
    
    import java.util.Scanner;
    
    /**
     * @author lizhangyu
     * @date 2021/3/6 12:45
     */
    public class HashTableDemo {
    
        public static void main(String[] args) {
            HashTable hashTable = new HashTable(7);
            String key = "";
            Scanner scanner = new Scanner(System.in);
    
            while (true) {
                System.out.println("add: 添加雇员");
                System.out.println("list: 显示雇员");
                System.out.println("find: 查找雇员");
                System.out.println("exit: 退出系统");
                key = scanner.next();
                switch (key) {
                    case "add" :
                        System.out.println("请输入员工id");
                        int id = scanner.nextInt();
                        System.out.println("请输入员工名字");
                        String name = scanner.next();
                        Employee employee = new Employee(id, name);
                        hashTable.add(employee);
                        break;
                    case "find" :
                        System.out.println("请输入员工id");
                        id = scanner.nextInt();
                        hashTable.find(id);
                        break;
                    case "list" :
                        hashTable.list();
                        break;
                    case "exit" :
                        scanner.close();
                        System.exit(0);
                    default:
                        break;
                }
            }
        }
    }

[Hi _ RHi_key_ i _1_2_..._k]: https://private.codecogs.com/gif.latex?%5Cdpi%7B100%7D%20%5Cbg_red%20Hi%20%3D%20RHi%28key%29%2C%20i%20%3D1%2C2%2C...%2Ck