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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了Hash算法的设计原理与代码实现，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3892字，纯文字阅读大概需要6分钟。

内容图文

一：Hash算法的设计原理

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

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

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

• 除留余数法

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

• 伪随机数法

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

二：处理Hash冲突的方法

• 再哈希法

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

                   

当哈希地址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;
            }
        }
    }
}

 

内容总结

以上是互联网集市为您收集整理的Hash算法的设计原理与代码实现全部内容，希望文章能够帮你解决Hash算法的设计原理与代码实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---