🚩哈希表（Java实现）

📚哈希表定义

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

哈希表可以提供快速的插入和查找工作，哈希表运算的非常快，而且编程实现也比较容易。哈希表是数组和链表结构。

📗哈希表的内存结构示意图

在散列表中，不像普通数组，每个格子里存放的是一个单一的数据，而是在每一个格子中存放的是一个链表。如图：

📕哈希表存储示意

哈希表是根据关键码值（key value）而直接进行访问的数据结构，通过一个散列函数来将码、键进行映射。所以我们需要提前编写一个规则，即函数y = f(key); 在存储和访问时，我们通过k进行计算，得到一个位置来进行存储或访问。

举个例子，如下一个简单的哈希表，我们给出一个关于取模操作的散列函数 y = f(key) = key % 5

现在我们需要插入员工的信息，以员工的编号作为key值，比如我们先插入 （1，吕布） 员工，经过散列函数计算，1 % 7 = 1，所以我们要将该数据插入到数组下标为1的位置去。

同理，我们也将 （2，王昭君），（3，赵云），（8，貂蝉） 数据插入到哈希表中。

📘代码演示

📭项目背景

有一个公司，当有新的员工来报道时，要求将该员工的信息加入（id，姓名），当输入该员工的id时，要求可以查到该员工的所有信息。
要求： 不使用数据库，尽量节省内存，速度越快越好（哈希表）。

📬员工Emp类

public class Emp {
    private int id;
    private String name;
    private Emp next;

    public Emp(int id, String name) {
        this.id = id;
        this.name = name;
    }

    public int getId() {
        return id;
    }
    
	public String getName() {
        return name;
    }
    
    public Emp getNext() {
        return next;
    }
    
    public void setNext(Emp next) {
        this.next = next;
    }
}

📪链表结构EmpLinkedList类

包含add添加员工操作，list显示员工信息操作，findEmpById查找员工操作，deleteEmp删除员工操作。

public class EmpLinkedList {
    private Emp head;
    
    //添加员工
    public void add(Emp emp) {
        //添加的是第一个员工
        if (head == null) {
            head = emp;
            return;
        }

        //添加的不是第一个员工
        Emp curemp = head;
        while (true) {
            if (curemp.getNext() == null) {
                break;
            }
            curemp = curemp.getNext();
        }
        curemp.setNext(emp);
    }

    //遍历链表的雇员信息
    public void list(int no) {
        if (head == null) {
            System.out.println("第" + (no + 1) +"条链表为空");
            return;
        }

        Emp curemp = head;
        System.out.print("第" + (no + 1) +"条链表信息为：");
        while (true) {
            System.out.printf("员工id：%d\t 员工姓名：%s\t",curemp.getId(),curemp.getName());
            if (curemp.getNext() == null) {
                break;
            }
            curemp = curemp.getNext();
        }
        System.out.println();
    }


    //通过员工编号查找员工
    public Emp findEmpById(int id) {
        if (head == null) {
            System.out.println("链表为null");
            return null;
        }

        Emp curemp = head;
        while(true) {
            if (curemp.getId() == id) {
                return curemp;
            }
            if (curemp.getNext() == null) {
                curemp = null;
                break;
            }
            curemp = curemp.getNext();
        }
        return curemp;
    }

    //通过员工编号删除员工
    public boolean deleteEmp(int id) {
        if (head == null) {
            return false;
        }

        if (head.getNext() == null && head.getId() == id) {
            head = null;
            return true;
        }

        Emp curemp = head;
        while(true) {
            if (curemp.getNext().getId() == id) {
                curemp.setNext(curemp.getNext().getNext());
                return true;
            }
            if (curemp.getNext().getNext() == null) {
                break;
            }
        }
        return false;
    }
}

📫HashTab类

public class HashTab {
    private EmpLinkedList[] empLinkedListArray;
    int size;

    public HashTab(int size) {
        this.size = size;
        empLinkedListArray = new EmpLinkedList[size];
        for (int i = 0;i < size;i++) {
            empLinkedListArray[i] = new EmpLinkedList();
        }
    }

    //添加雇员
    public void add(Emp emp) {
        int emplinkedListArrayNo = hashFun(emp.getId());
        empLinkedListArray[emplinkedListArrayNo].add(emp);
    }

    //遍历所有的链表
    public void list() {
        for (int i = 0; i < size; i++) {
            empLinkedListArray[i].list(i);
        }
    }

    //查找
    public void findEmpById(int id) {
        int emplinkedListArrayNo = hashFun(id);
        Emp emp = empLinkedListArray[emplinkedListArrayNo].findEmpById(id);
        if (emp == null) {
            System.out.println("没有找到~~");
        }else {
            System.out.printf("找到了，在第%d条链表中，id = %d",emplinkedListArrayNo + 1,id);
        }
        System.out.println();
    }

    //删除员工
    public void deleteEmp(int id) {
        int emplinkedListArrayNo = hashFun(id);
        boolean res = empLinkedListArray[emplinkedListArrayNo].deleteEmp(id);
        if (res) {
            System.out.println("删除成功");
        }else {
            System.out.println("没有此员工");
        }
    }

    //散列函数 取模法
    public int hashFun(int id) {
        return id % size;
    }
}

📭哈希表测试类HashTabDemo

import java.util.Scanner;

public class HashTabDemo {
    public static void main(String[] args) {
        HashTab hashTab = new HashTab(7);

        int key = -1;
        Scanner scanner = new Scanner(System.in);
        while (true) {
            System.out.println("--------1.添加雇员-----------");
            System.out.println("--------2.显示雇员-----------");
            System.out.println("--------3.查找雇员-----------");
            System.out.println("--------4.删除雇员-----------");
            System.out.println("--------0.退出系统-----------");
            key = scanner.nextInt();
            switch (key) {
                case 1:
                    System.out.println("请输入雇员id");
                    int id = scanner.nextInt();
                    System.out.println("请输入雇员姓名");
                    String name = scanner.next();
                    Emp emp = new Emp(id, name);
                    hashTab.add(emp);
                    break;
                case 2:
                    hashTab.list();
                    break;
                case 3:
                    System.out.println("请输入要查找的员工编号");
                    id = scanner.nextInt();
                    hashTab.findEmpById(id);
                    break;
                case 4:
                    System.out.println("请输入要删除的员工编号");
                    id = scanner.nextInt();
                    hashTab.deleteEmp(id);
                    break;
                case 0:
                    scanner.close();
                    System.exit(0);
                    break;
            }
        }
    }
}

📫结果演示

🃏哈希算法

🎃哈希算法定义

由于哈希算法被计算的数据是无限的，而计算后的结果范围有限，因此总会存在不同的数据经过计算后得到的值相同（两个不同的数据计算后的结果一样）。当我们对某个元素进行哈希运算，得到一个存储地址，然后根据地址进行元素的存储操作。

🎄哈希碰撞定义

要进行插入的时候，发现已经被其他元素占用了，其实这就是所谓的哈希冲突，也叫哈希碰撞。哈希函数的设计至关重要，好的哈希函数会尽可能地保证计算简单和散列地址分布均匀,但是，我们需要清楚的是，数组是一块连续的固定长度的内存空间，再好的哈希函数也不能保证得到的存储地址绝对不发生冲突。那么哈希冲突如何解决呢？

🎋解决哈希碰撞的方式

🌄线性探测法

⛵思想

主要根据index = val.hashcode()%element.length来解决哈希冲突问题。从数组当前位置（hashcode()）开始，找到下一个空位置，进行存放。当数组填充满之后，进行数组的扩容操作，继续存放值。存储的键值对中键相等进行值的覆盖操作。进行扩容后的操作，还得进行元素的重新哈希操作。

🚤代码实现

import java.util.Arrays;
import java.util.Map;

//线性探测法
public class LineHashMap<K extends Comparable<K>, V extends Comparable<K>> {
    private static final double LOAD_FACTOR = 0.75;//扩容因子
    private static final int INIT_CAPACITY = 1 << 4;//默认初始化大小 16
    private Entry<K, V>[] table;
    private int size;//有效个数

    public LineHashMap() {
        table = new Entry[INIT_CAPACITY];
        this.size = 0;
    }

    public V get(K key) {//有数据 index key 相等 2.有数据 发生冲突 3.没有该数据
        int index = key.hashCode() % table.length;
        //如果发生哈希冲突
        if (table[index].key.compareTo(key) != 0) { //对象比较方式?
            int count = 0;
            int i = index;
            for (; table != null && table[index].key.compareTo(key) != 0; i = ++i % table.length) {
//                count++;
//                if (count == table.length) {
//                    System.out.println("没有该数据");
//                    return null;
//                }
            }
            return table[i].value == null ? null : table[i].value;
        }

        return table[index].value;
    }

    public void rehash() {
        if ((double) size / table.length >= LOAD_FACTOR) {
            Entry<K, V>[] newtable = new Entry[table.length << 1];

            for (int i = 0; i < table.length; i++) {
                int index = table[i].key.hashCode() % newtable.length;
                if (table[i] != null) {
                    if (newtable[index] == null) {
                        newtable[index] = table[i];
                    } else {
                        int j = index;
                        for (; newtable[j] != null; j = ++j % newtable.length) {

                        }
                        newtable[j] = table[i];
                    }
                }
            }
            table = newtable;
        }
    }

    public void put(K key, V value) {
        rehash();
        Entry<K, V> entry = new Entry<>(key, value);
        //需要将entry 放置到下标index = entry.key.hashcode() % table.length
        int index = entry.key.hashCode() % table.length;
        if (table[index] == null) {
            table[index] = entry;
        } else {
            int j = index;
            for (; table[j] != null; j = ++j % table.length) {

            }
            table[j] = entry;
        }
        size++;
    }


    //Entry 静态内部类
    static class Entry<K, V> implements Map.Entry<K, V> {
        private K key;
        private V value;

        public Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }

        @Override
        public K getKey() {
            return null;
        }

        @Override
        public V getValue() {
            return null;
        }

        @Override
        public V setValue(V value) {
            return null;
        }
    }
}

🌅链地址法

线性探测法当产生哈希冲突的键值对越多，遍历数组的次数就会越多。为了解决这个问题，我们采用数组和链表结合的方式，数组元素是一个链表结构，产生哈希冲突，在相同的索引下标下进行链表的插入操作。

🏕️思想

不足：

① 链地址法存在的不足在于，当产生哈希冲突的节点越多，那么数组索引下标查找就会变成链表的遍历操作。数组的优势在于随机取值，时间复杂度达到O(1)，而链表的查找时间效率达到O(n)。
② 当产生数组扩容时，所有的元素节点都必须进行重新哈希。

🏞️代码实现

import java.util.Map;

public class MyLinkedHashMap<K,V> {
    private static final int INIT_CAPACITY = 1 << 14;
    private static final double LOAD_FACTOR = 0.75;
    private Node<K,V>[] table;
    private int size;//有效个数，数组被占个数

    public MyLinkedHashMap() {
        table = new Node[INIT_CAPACITY];
    }



    public void rehash() {
        //扩容
        if ((float)size / table.length >= LOAD_FACTOR) {
            Node<K,V>[] newtable = new Node[table.length << 1];
            size = 0;
            for (int i = 0;i < table.length;i++) {
                if (table[i] != null) {
                    Node<K,V> p = table[i];
                    for (;p != null; p = p.next) {
//                        int index = p.n_value.key.hashCode() % newtable.length;
//                        if (newtable[index] != null) {
//                            p.next = newtable[index];
//                            p = newtable[index];
//                        }else {
//                            newtable[index] = p;
//                        }
                        put(p.n_value.key,p.n_value.e_value);
                    }
                }
            }
            table = newtable;
        }
    }

    public void put(K key,V val) {
            rehash();
       Node<K,V> node = new Node<>(key,val,null);
        //扩容？重新哈希
        rehash();
        int index = key.hashCode() % table.length;
        if (table[index] != null) {
            node.next = table[index];
            table[index] = node;
        }else {
            table[index] = node;
        }
        size++;
    }

//    public V get(K key) {
//        int index = key.hashCode() % hashCode();
//        if (table[index] == null) {
//            System.out.println("没有该值");
//            return null;
//        }
//    }

    static class Node<K,V> {
        Entry<K,V> n_value;
        Node<K,V> next;

        public Node(K key,V value, Node<K, V> next) {
            this.n_value = new Entry<>(key,value);
            this.next = next;
        }
    }

    static class Entry<K, V>  { //键值对
        private K key;
        private V e_value;

        public Entry(K key, V value) {
            this.key = key;
            this.e_value = value;
        }
    }
}