哈希表

概念介绍

　　有同学想了解哈希表，今天它来了！哈希表也叫做散列表，是一种根据Key值而直接进行访问的数据结构。它通过把Key值映射到表中一个位置来访问所存储的元素，对Key值进行映射的函数我们称之为散列函数，而存放记录的数组叫做散列表（概念如果不好理解，大家可以略过）。

　　概念有时很抽象，咱们举个简单的栗子进行说明。

　　现在咱们定义一个长度为10的数组用以进行数据进行存储，它长这个样子。

　　有一个同学，学号为1的小明同学，咱们需要把他的信息存储到数组中，该怎么添加和查找呢？

　　咱们先简单的定义散列函数：取模，即f(Key)=Key%10，f(1) = 1%10 =1,即将小明同学的信息放入数组的a[1]的位置，查找的时候，也是同样的道理，先对Key进行hash，然后找，hash表是不是很简单呢？

　　但是现在有一个学号为11的小王同学的信息也要添加进来，根据散列函数f(Key)=Key%10，f(11)=1。位置和小明冲突了，hash表是支持一山可容二虎的，该怎么做呢？用咱们原来学过的链表来处理，就行了。

　　最终结果，如图

代码实现

　　1、先定义学生对象

1 class Student {
2     public int id;
3     public String name;
4 
5     public Student(int id, String name) {
6         this.id = id;
7         this.name = name;
8     }
9 }

　　2、定义咱们的hash表结构为数组+链表，简单的hash实现，取模处理

 1 public class HashTable {
 2 
 3     private LinkedList[] studentLinkedListArray;
 4     private int size;
 5 
 6     public HashTable(int size) {
 7         this.size = size;
 8         studentLinkedListArray = new LinkedList[size];
 9     }
10 
11     private  int hash(int id) {
12         return id % size;
13     }
14 }

　　3、添加学生的方法，hash找到数组下标的位置，再添加

 1     public void add(Student stu) {
 2         // 先对id进行hash,找到放入数组的下标位置
 3         int no = hash(stu.id);
 4         if(studentLinkedListArray[no]==null){
 5             LinkedList<Student> linkedList = new LinkedList<>();
 6             linkedList.add(stu);
 7             studentLinkedListArray[no] = linkedList;
 8         }
 9         else {
10             studentLinkedListArray[no].add(stu);
11         }
12     }

　　4、实现根据id查询对象的方法

 1     public void getById(int id){
 2         // 先对id进行hash,找到数组的下标位置
 3         int no = hash(id);
 4         if(studentLinkedListArray[no]==null){
 5             System.out.printf("没有找到id为%d的学生",id);
 6         }
 7         else {
 8             // 遍历链表中的节点，根据id判断元素是否存在
 9             Iterator it = studentLinkedListArray[no].iterator();
10             while (it.hasNext()){
11                 Student stu = (Student)it.next();
12                 if(id == stu.id){
13                     System.out.printf("找到id为%d的学生",id);
14                     return;
15                 }
16             }
17             System.out.printf("没有找到id为%d的学生",id);
18         }
19     }

　　打完收工，Git地址：https://github.com/HollowCup/algorithms-and-data-structure，具体实现位于data-structure工程下的hash目录，如果发现不足之处，请联系我进行更改，十分感谢！关注我，为你介绍更多数据结构！