Java数据结构：哈希表

1.基本介绍

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

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

  
  

• 若关键字为k，则其值存放在f(k)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数，按这个思想建立的表为散列表。

• 对不同的关键字可能得到同一散列地址，即k1 ≠k2，而f(k1)=f(k2)，这种现象称为冲突（英语：Collision）。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述，根据散列函数f(k)和处理冲突的方法将一组关键字映射到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表便称为散列表，这一映射过程称为散列造表或散列，所得的存储位置称散列地址。

• 若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数（Uniform Hash function），这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。

2.实际题目

google公司的一个上机题:
有一个公司,当有新的员工来报道时,要求将该员工的信息加入(id,性别,年龄,名字,住址..),当输入该员工的id时,要求查找到该员工的所有信息.

• 题目思路：

由图可知我们需要创建三个类及其对应方法
1.HashTable类 （相当于图中蓝色部分）
2.EmpLinkedList类 （相当于图中绿色部分）
3.Emp类 （相当于图中黑色部分）

//Emp类
class Emp{
public int id;
public String name; 
public Emp next;
//构造方法
public Emp(int id, String name) {
    super();
    this.id = id;
    this.name = name;
}
@Override
public String toString() {  
    return "HeroNode [id=" + id + ", name=" + name +  "]";
}
 }


 // HashTable类
class HashTable{
 private EmpLinkedList[] emplist;
private int size;
public HashTable(int size) {
    this.size = size;
    emplist = new EmpLinkedList[size];
    for(int i = 0;i < emplist.length;i++) {
        emplist[i] = new EmpLinkedList();
    }
}   
public void list() {
    for(int i = 0;i < size;i++) {
        if(emplist[i].isEmpty()) {
            System.out.println("第"+i+"个节点链表为空");
        }else {
            System.out.println("第"+i+"个节点链表为:");
            emplist[i].list();
        }
    }
}   
public void findEmp(int id) {
    int index = 0;
    boolean flag = false;
    while(true) {
        if(emplist[index].findById(id) != null) {
            break;
        }
        if(index == emplist.length-1) {
            if(emplist[index].findById(id) == null) {
            flag = true;
            }
            break;
        }
        index++;
    }
    if(flag) {
        System.out.println("未找到该数据");
    }else {
        System.out.println("在第"+index+"个节点找到数据："+emplist[index].findById(id));
    }
}   
public void add(Emp emp) {
    int tableIndex = hashFun(emp.id);
    emplist[tableIndex].add(emp);
}   
//编写散列函数
public int hashFun(int id) {
    return id % size;
}
}


//EmpLinkedList类
class EmpLinkedList{
private Emp head;   
public void add(Emp emp) {
    if(head == null) {
        head = emp;
        return;
    }
    Emp temp = head;
    while(true) {
        if(temp.next == null) {
            break;
        }
        temp = temp.next;
    }
    temp.next = emp;
}   
public boolean isEmpty() {
    if(head == null) {
        return true;
    }else {
        return false;
    }
}   
public void list() {
    if(isEmpty()) {
        System.out.println("链表为空");
    }
    Emp temp = head;
    while(true) {           
        System.out.println(temp.toString());
        if(temp.next == null) {
            break;
        }
        temp = temp.next;
    }       
}
public Emp findById(int id) {
    if(isEmpty()) {
        return null;
    }
    Emp temp = head;
    while(true) {
        if(temp.id == id) {
            return temp;
        }
        if(temp.next == null) {
            return null;
        }
        temp = temp.next;
    }
}

• 然后再到main方法中测试数据:

   public static void main(String[] args) {
      HashTable table = new HashTable(10);
      Emp emp1 = new Emp(1,"一号");
      Emp emp2 = new Emp(2,"二号");
      Emp emp3 = new Emp(21,"二一号");
      table.add(emp1);
      table.add(emp2);
      table.add(emp3);
      table.findEmp(2);
     
    }