哈希表

介绍：

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

给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。

img

常见的形式：

• 数组+链表

• 数组+二叉树

实战：手写hash

哈希表(散列)-Google.上机题

1. 看一个实际需求，google公司的一个上机题:
2. 有一个公司，当有新的员工来报道时，要求将该员工的信息加入(id,性别年龄住址.),当输入该员工的id时，要求查
   找到该员工的所有信息.
   3)要求:不使用数据库尽量节省内存，速度越快越好=>哈希表(散列)

要求:

1)不使用数据库，速度越快越好=>哈希表(散列)
2)添加时，保证按照id从低到高插入[课后思考:如果id不是从低到高插入，但要求各条链表仍是从低到
高，怎么解决?]
3)使用链表来实现哈希表，该链表不带表头[即:链表的第-个结点就存放雇 员信息]
4)思路分析并画出示意图

image-20200728163016265.png

目标：数组+链表

• Emp存放雇员信息
  1. id
  2. name
  3. next
• EmpLinkedList 来当做链表
  1. head
• HashTab 来管理所有的链表

hash我们通过hash函数来定位位置，通过取模的方式。

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

HashTab

class HashTab{
    public EmpLinkedList[] empLinkedListArr;
    private int size ;
    // 初始化
    public HashTab(int size) {
        this.empLinkedListArr = new EmpLinkedList[size];
        this.size = size;
        for (int i = 0; i < empLinkedListArr.length; i++) {
            empLinkedListArr[i] = new EmpLinkedList();
        }
    }
    //添加雇员
    public void add(Emp emp){
        int id = hashFun(emp.id);
        empLinkedListArr[id].add(emp);
    }

    //遍历
    public void list(){
        for (int i = 0; i < size; i++) {
            empLinkedListArr[i].list();
        }
    }

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

    //通过id查找雇员
    public void findEmpById(int id){
        Emp emp = empLinkedListArr[hashFun(id)].findEmpById(id);
        if (emp==null){
            System.out.println("没有找到雇员");
        }else {
            System.out.println("在第"+(hashFun(id)+1)+"个链表中"+emp);
        }
    }
}

Emp

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

    @Override
    public String toString() {
        return "Emp{" +
                "id=" + id +
                ", name='" + name +
                '}';
    }
}

EmpLinkedList

class EmpLinkedList{
    private Emp head;
    //添加
    public void add(Emp emp){
        if (head==null){
            head = emp;
            return;
        }
        Emp cur = head;
        while (true){
            if (cur.next==null){
                break;
            }
            cur = cur.next;
        }
        cur.next = emp;
    }
    //遍历
    public void list(){
        if (head==null){
            System.out.println("链表为空");
            return;
        }
        Emp cur = head;
        while (true){
            System.out.print("id="+cur.id+"name="+cur.name+"=>");
            if (cur.next==null){
                break;
            }
            cur = cur.next;
        }
        System.out.println();
    }

    //通过id查找雇员
    public Emp findEmpById(int id){
        if (head==null){
            return null;
        }
        Emp cur = head;
        while (true){
            if (cur.id == id){
                break;
            }
            if (cur.next==null){
                cur = null;
                break;
            }
            cur = cur.next;
        }
        return cur;
    }
}

test

public class HashTabDemo {
    public static void main(String[] args) {
        HashTab hashTab = new HashTab(4);
        for (int i = 0; i < 20; i++) {
            hashTab.add(new Emp(i,"23232"));
        }
        hashTab.list();
        hashTab.findEmpById(18);
    }
}

结果

image-20200728160756743.png

\image-20200728160756743.png)