苏州建设交通高等职业技术学校/sem优化师是做什么的

什么是哈希表

我的理解：给定一些数据，这些数据可以是基本的数据类型，也可以是引用数据类型，当然也可以是对象，比如链表啥的。
然后使用一个函数，对数据计算出一个值，这个值对应这个数据，后期查找的时候，可以根据这个一一对应的关系更快速的查找数据。
就好像是字典，这个函数就是散列函数。
举个例子，以组数据1，7，26，21，无序的，根据一个函数，x%size，即对每个数据取模运算，size=数据的长度=4，然后计算出来的值分别为0，3，2，1，然后根据这些值就可以把这组数据放入对应位置的数组内，而这个位置就是计算出来的值。
以上是最简单的例子，其中还有很多细节需要注意，比如计算出的值有冲突，也就是说索引可能一样等等，这里就不深入说明了。

另外，我的理解是，计算出的值不一定就是对应那个值本身的，有可能是只是缩小了这个值所在的范围而已，比如一个数组链表，这个数组装链表，链表内装的是雇员信息，如id，姓名，年龄等，根据id，采用某个函数，计算出其处于哪个链表中，然后再在这个链表中进行查找，查询速度就会加快，为什么呢，假如所有的雇员都在一个链表中，那么链表很长查询速度就会很慢，但是经过散列函数处理后，相当于链表被打断了，分成了多个链表，在更短的链表中查找会更快。
当然查询使用到了散列函数，添加元素的时候也自然使用到了，也就是说，确定将元素放到哪个链表中。

以下代码就实现雇员信息的哈希表的创建等操作

Java代码实现

/*** 先创建一个链表，用于装雇员信息，这个链表实现的功能包括添加元素，遍历元素* 再创建一个哈希表，底层是数组，用于存放链表，哈希表实现的功能包括添加元素，遍历元素，* 这些方法其实来自于链表，只是哈希表根据一个散裂函数确定操作那个链表而已* 注意，对外调用的方法是哈希表*/package mypackage;//雇员链表
class EmpLinkList{
//    第一个节点和最后一个节点public Node head;public Node last;//    添加雇员,新进的雇员直接加在链表的尾部即可public void add(int id, String name, int age,Node next){
//        如果链表不为空if (head!=null){Node newnode=new Node(id,name,age,next);last.next=newnode;last=newnode;
//      如果链表为空}else {Node newnode=new Node(id,name,age,next);head=newnode;last=newnode;}}//    遍历雇员public void ergodic(int i){
//        如果为空if (head==null){System.out.println("第"+(i+1)+"个链表为空");return;//如果不为空}else {System.out.print("第"+(i+1)+"个链表的内容为：");Node node=head;while (node!=null){System.out.print("->>>"+"id="+node.id+","+"name="+node.name+","+"age="+node.age);node=node.next;}}System.out.println();}//    查找雇员public Node serch(int id){//        如果为空if (head==null){System.out.println("链表为空");return null;//        如果不为空}else {Node node=head;while (node!=null){if (node.id==id){return node;}else {node=node.next;}}}return null;}//节点类class Node{int id;String name;int age;Node next;public Node(int id, String name, int age,Node next) {this.id = id;this.name = name;this.age = age;this.next = next;}}
}//哈希表，核心在这里
class hashTab{
//    数组，用于装各个链表private EmpLinkList[] empLinkListArrays;
//    数组的大小private int size;//    构造方法，初始化数组的大小
//    特别注意要初始化每个链表,一定要初始化每个链表public hashTab(int size) {this.size=size;this.empLinkListArrays = new EmpLinkList[size];
//        初始化每个链表for (int i = 0; i <size; i++) {empLinkListArrays[i]=new EmpLinkList();}}//    散列函数,作用为根据id将这个雇员放在那个链表内public int hashfunc(int id){
//        取模的散裂函数return id % size;}
//    添加雇员public void add(int id, String name, int age, EmpLinkList.Node next){
//        根据id确定添加到哪条链表int num=hashfunc(id);empLinkListArrays[num].add(id,name,age,next);}
//    遍历所有雇员，就要遍历所有链表public void ergodic(){for (int i = 0; i <size ; i++) {empLinkListArrays[i].ergodic(i);}}
//    输入id查找雇员public void serch(int id){
//        根据id确认在那个链表中查找int num=hashfunc(id);EmpLinkList.Node node=empLinkListArrays[num].serch(id);if (node==null){System.out.println("没有找到这个雇员");}else {System.out.println("雇员信息为："+"id="+node.id+","+"name="+node.name+","+"age="+node.age);}}
}//测试
public class MyJava {public static void main(String[] args) {hashTab hashtab=new hashTab(10);hashtab.add(23,"小王",18,null);hashtab.add(10,"小李",20,null);hashtab.add(20,"小孙",19,null);hashtab.add(60,"小美",25,null);
//        遍历元素System.out.println("遍历雇员：");hashtab.ergodic();System.out.println("-----------------------------");//        根据id查找System.out.println("查找雇员：");hashtab.serch(60);}
}

结果：