HashTable

Hash结构优势

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

这样的合理安排的数据结构，便可以是得我们可以利用分而治之的思想进行数据的处理于存储，而不同于链表与数组有着先天性的限制。

当然Hash也是有着美中不足的缺陷的，比如表需要安排多少个链表，hash值又该任何分配，这都是需要灵活变化的。对于小白来说看一下主流语言的API实现或许就有启发。

散列函数

关键代码
1
2
3
4
5
6
7
8
9
10
11
private int hashFun(int id) {
   
   int hashIndex = id % size;
   
   if (hashIndex < size) {
     return hashIndex;
   } else {
     System.out.println("hashTable‘s function  hashFun is error");
     return -1;
   }
 }
一般的线性表，树中，记录在结构中的相对位置是随机的，即和记录的关键字之间不存在确定的关系，因此，在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较“的基础上，查找的效率依赖于查找过程中所进行的比较次数。

理想的情况是能直接找到需要的记录，因此必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应。

冲突

无论哈希函数设计有多么精细，都会产生冲突现象，也就是2个关键字处理函数的结果映射在了同一位置上，因此，有一些方法可以避免冲突。

拉链法

拉出一个动态链表代替静态顺序存储结构，可以避免哈希函数的冲突，不过缺点就是链表的设计过于麻烦，增加了编程复杂度。此法可以完全避免哈希函数的冲突。

多哈希法

设计二种甚至多种哈希函数，可以避免冲突，但是冲突几率还是有的，函数设计的越好或越多都可以将几率降到最低（除非人品太差，否则几乎不可能冲突）。

开放地址法

开放地址法有一个公式：Hi=(H(key)+di) MOD m i=1,2,…,k(k<=m-1）

其中，m为哈希表的表长。di 是产生冲突的时候的增量序列。如果di值可能为1,2,3,…m-1，称线性探测再散列。如果di取1，则每次冲突之后，向后移动1个位置.如果di取值可能为1,-1,4,-4,9,-9,16,-16,…kk,-kk(k<=m/2）

称二次探测再散列。如果di取值可能为伪随机数列。称伪随机探测再散列。

建域法

假设哈希函数的值域为[0,m-1]，则设向量HashTable[0..m-1]为基本表，另外设立存储空间向量OverTable[0..v]用以存储发生冲突的记录。

代码思路

google 公司的一个上机题

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

代码案例

代码链接👌

package DataStructures.hashTable;

/**
 * @author yichangkong
 * @create 2020-05-06-14:53
 */
class HashTableDome {
  public static void main(String[] args) {

    HashTable hashTable = new HashTable(10);
    Emp emp3 = new Emp("ts3", 3);
    Emp emp2 = new Emp("ts2", 2);
    Emp emp1 = new Emp("ts1", 1);

    hashTable.add(emp3);
    hashTable.add(emp2);
    hashTable.add(emp1);
    hashTable.getlist();
    hashTable.fundEmpById(4);
  }
}

class HashTable {
  private EmpLinkedList[] empLinkedListsArray;

  private int size;

  public HashTable(int size) {
    this.size = size;
    empLinkedListsArray = new EmpLinkedList[size];

    // 初始化哈希表
    for (int i = 0; i < size; i++) {
      empLinkedListsArray[i] = new EmpLinkedList();
    }
  }

  public void add(Emp emp) {
    int hashIndex = hashFun(emp.id);
    empLinkedListsArray[hashIndex].add(emp);
  }

  private int hashFun(int id) {

    int hashIndex = id % size;

    if (hashIndex < size) {
      return hashIndex;
    } else {
      System.out.println("hashTable‘s function  hashFun is error");
      return -1;
    }
  }

   void getlist() {
    for (int i = 0; i < size; i++) {
      empLinkedListsArray[i].getlist();
    }
  }

   void fundEmpById(int id) {
    int hashIndex = hashFun(id);
    Emp emps = empLinkedListsArray[hashIndex].fundEmpById(id);
    System.out.println(emps);
  }
}

/** @Description 表示一个链表雇员，对象 @Param id name next 默认为空 @Return @Date 2020/5/18 @Time 11:47 */
class Emp {
  int id;
  String name;
  Emp next;

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

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

class EmpLinkedList {

  Emp head;

  /** @Description 添加方法 @Param [emp] @Return void @Date 2020/5/6 @Time 15:12 */
  public void add(Emp emp) {
    // 因为默认为空
    if (head == null) {
      head = emp;
      return;
    }
    Emp temEmp = head;
    // 遍历循环到链表的最后一个值
    while (true) {
      if (temEmp.next == null) {
        break;
      }
      temEmp = temEmp.next;
    }
    // 添加到这个链表又如何和head链表产生关系呢？
    temEmp.next = emp;
  }

  /** @Description 打印链表 @Param [] @Return void @Date 2020/5/6 @Time 15:15 */
   void getlist() {

    if (head == null) {
      System.out.println("此链表并没有数据");
      return;
    }
    Emp tempEmp = head;
    while (true) {
      System.out.printf("=> id=%d name=%s\t", tempEmp.id, tempEmp.name);
      if (tempEmp.next == null) {
        break;
      }
      tempEmp = tempEmp.next;
    }
    System.out.println();
  }
  /**
   * @Description 单链表里查询雇员信息 @Param [id] @Return DataStructures.hashTable.Emp @Date 2020/5/6 @Time
   * 17:10
   */
  Emp fundEmpById(int id) {
    if (head == null) {
      return null;
    }
    Emp tempEmp = head;
    while (true) {
      if (tempEmp.id == id) {
        return tempEmp;
      }
      if (tempEmp.next == null) {
        return null;
      }
      tempEmp = tempEmp.next;
    }
  }
}