更多内容，前往 IT-BLOG
哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。
数组的优缺点是：寻址容易，插入和删除困难；
链表的优缺点是：寻址困难，插入和删除容易；
我们综合两者的特性，做出一种寻址容易，插入删除也容易的数据结构？答案是肯定的，这就是我们要提起的哈希表，哈希表有多种不同的实现方法，我接下来解释的是最常用的一种方法——拉链法，我们可以理解为“链表的数组”，如图：左边很明显是个数组，数组的每个成员包括一个Head指针，指向一个链表的头，当然这个链表可能为空，也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去，也是根据这些特征，找到正确的链表，再从链表中找出这个元素。
Hash表代码展示：这里的链表直接使用了 JDK默认的链表（LinkedList），比较简单如果自己实现更好点。如果自己动链表的实现则直接使用 JDK提供的即可，不懂最好学一下链表的使用。自己实现一个链表。HashTable底层的链表 Head 指针永远指向第一个元素，如果没有元素则为空。增删改查操作都是从 Head 链表开始向下遍历即可。HashTable的查询速度非常的快，几乎是 O(1)的时间复杂度，hash就是找到一种数据内容和数据存放地址之间的映射关系。而散列法指元素特征转变为数组下标的方法。
1 package com.algorithms;
2
3 import java.util.Iterator;
4 import java.util.LinkedList;
5
6 /**
7 * hashTabe 哈希表的应用分析：
8 * 【1】HashTable是由数组和链表组成
9 * 【2】创建需要的数组大小
10 * 【3】创建链表：这里我就直接使用JDK提供的linkedList 链表了
11 * 【4】hashTabel中需要存放对象，我们先创建自己要存放的对象 Emp
12 * 【5】思想：将emp的no根据最简单的散列函数（取模）算出要存放的下标，接着将数据顺序的存放在链表中
13 * 【6】问题：简单的散列算法，会导致数据分布不均匀，会出现长链表。HashMap中使用key的hashcode然后在于分配大小的2的幂次数进行位运算计算
14 */
15
16 public class HashTable {
17 //定义一个数组
18 private LinkedList[] arry;
19 //用户定义的hashTable的大小
20 private int size;
21
22 //构造函数，初始化数组和链表
23 public HashTable(int size){
24 this.size = size;
25 arry = new LinkedList[size];
26 //对链表进行初始化
27 for(int i = 0;i<size;i++){
28 //这里的链表我们就直接用 LinkedList 了JDK提供的，不自己手动写了。
29 arry[i] = new LinkedList();
30 }
31 }
32
33 //向数组中插入元素 【增】
34 public void put(Emp emp){
35 if(emp == null){
36 throw new IllegalArgumentException("传入的参数为空");
37 }
38 //首先获取 emp 的no对其取模
39 int index = emp.getNo() % size;
40 arry[index].add(emp);
41 }
42
43 //删除节点 【删】
44 public void del(Emp emp){
45 if(emp == null){
46 throw new IllegalArgumentException("传入的参数为空");
47 }
48 //首先获取 emp 的no对其取模
49 int index = emp.getNo() % size;
50 arry[index].remove(emp);
51 }
52
53 //查询链表中的元素 【列表】
54 public void list(){
55 for(int i=0;i<size;i++){
56 Iterator iterator = arry[i].iterator();
57 System.out.printf("展示第%d个链表内容：",i+1);
58 while(iterator.hasNext()){
59 Emp emp = (Emp)iterator.next();
60 System.out.printf(""+emp);
61 }
62 System.out.println("");
63 }
64 }
65
66 //主函数觉得不是很重要，放最后了，用来测试
67 public static void main(String[] args) {
68
69 HashTable hashTable = new HashTable(6);
70 //组装数据
71 hashTable.put(new Emp(1,"曹操"));
72 hashTable.put(new Emp(2,"刘备"));
73
74 hashTable.list();
75 }
76 }
77
78 class Emp{
79 private int no;
80 private String name;
81 //构造器
82
83 public Emp(int no, String name) {
84 this.no = no;
85 this.name = name;
86 }
87
88 public int getNo() {
89 return no;
90 }
91
92 public String getName() {
93 return name;
94 }
95
96 @Override
97 public String toString() {
98 return "Emp{" +
99 "no=" + no +
100 ", name='" + name + '\'' +
101 '}';
102 }
103 }
