哈希表

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。

在java中 hashMap 的底层就是数组+链表+红黑树。所以我们可以采用数组+链表来手写一个哈希表。

而我们一般的哈希函数都用除留余数法
H（key）=key MOD p （p<=m m为表长），key与表长做模运算
解决冲突的方法使用链地址法。

这里举个例子就是，看这张图
一共有数组一共16个元素。每个数组后边跟了一个链表，坦白了讲就是链表类型的数组。
现在我们需要存储 496
496 % 16 = 0，所以我们放在了下标为0这个位置链表上
我们需要存储896的时候，896 % 16 = 0，同样的我们也加在下标为0的链表上。
当我们需要存储1的时候，1 % 16 = 1，所以我们把他放在下标为1的链表上。

具体的散列函数和解决冲突的方法可以去哈希表百度百科了解

下边的代码实现也很简单，只要你的单链表掌握的不错，那么哈希表对你来讲也是没问题的。

public class HashTabTest {
    public static void main(String[] args) {
        Employee hash = new Employee(1, "halo");
        Employee hi = new Employee(2, "hi");
        Employee qi = new Employee(7, "qi");
        Employee hello = new Employee(1024, "hello");
        HashTab hashTab = new HashTab(6);
        hashTab.add(hash);
        hashTab.add(hi);
        hashTab.add(qi);
        hashTab.add(hello);
        hashTab.list();
        System.out.println(hashTab.find(13));
        hashTab.list();
    }
}
class HashTab {
    private EmployeeLinked[] linked;
    private Integer size;
    public HashTab(Integer size) {
        this.size = size;
        linked = new EmployeeLinked[size];
        //对数组中每个元素初始化
        for (int i = 0; i < size; i++) {
            linked[i] = new EmployeeLinked();
        }
    }
    public void add(Employee emp) {
        //首先使用散列函数根据传入的 emp.id ,计算存储在哪条链表
        int no = emp.id % size;
        linked[no].add(emp);
    }
    public void list() {
        //遍历的时候要遍历所有的数组链表
        for (int i = 0; i < size; i++) {
            linked[i].list(i);
        }
    }
    public Employee find(int id) {
        int no = id % size;
        return linked[no].findEmpById(id);
    }
}
//employee 链表
class EmployeeLinked {
    //头节点，指向第一个节点
    private Employee head;
    //向链表中添加新元素
    public void add(Employee node) {
        //如果头节点为null，那现在加入的元素就是头一个元素
        if (head == null) {
            head = node;
            return;
        }
        //不是第一个节点，那么我们就要定义一个辅助变量来找到最后一个节点
        Employee temp = head;
        //循环遍历到最后一个节点
        //如果temp.next == null,说明当前节点为最后一个节点
        while (temp.next != null) {
            // temp 指针后移，指向下一个节点
            temp = temp.next;
        }
        //将最后一个节点 next指向新的元素
        temp.next = node;
    }
    //遍历链表
    public void list(int i) {
        System.out.print("第"+ i +"条链表");
        if (head == null){
            System.out.println("->null");
            return;
        }
        Employee temp = head;
        while (temp != null) {
            System.out.print("->" + temp);
            temp = temp.next;
        }
        System.out.println();
    }
    public Employee findEmpById(int id) {
        if (head == null) {
            return null;
        }
        Employee temp = head;
        while (true) {
            if (temp.id == id) {
                return temp;
            }
            if (temp.next == null) {
                return null;
            }
            temp = temp.next;
        }
    }
}
class Employee {
    Integer id;
    String name;
    Employee next;
    public Employee(Integer id, String name) {
        this.id = id;
        this.name = name;
    }
    @Override
    public String toString() {
        return "Employee{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
}