[一篇详解哈希表]数据结构之哈希表(散列表)

✅作者简介：大家好,我是Philosophy7？让我们一起共同进步吧！🏆 📃个人主页：Philosophy7的csdn博客
🔥系列专栏： 👑哲学语录: 承认自己的无知，乃是开启智慧的大门
💖如果觉得博主的文章还不错的话，请点赞👍+收藏⭐️+留言📝支持一下博>主哦🤞

文章目录

• • 散列表
  • • 简介:
    • 为什么需要散列表?
    • 哈希函数的实现
    • 哈希表的代码

散列表

简介:

散列表又可以叫做哈希表，那什么是散列表呢? 现在就让我们深入研究一下吧
是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，或者叫哈希函数，存放记录的数组叫做散列表

为什么需要散列表?

通过上面的描述，相信大家都比较不理解，现在让我们来举一个例子让大家更好的理解散列表。

相信大家会经常用到某某词典，而每次去搜索一个单词，如果都去查询数据库，那么将会大大影响到这个查询效率，而如果我们去查找缓存的话那么就会大大的提升了我们查找的效率。

哈希函数的实现

以Java语言为例，这里以常用集合的HashMap，来看一看哈希函数在Java中的实现
我们都知道Java当中以及很多的面向对象语言，每一个对象都有属于自己的HashCode(哈希值)，这个哈希值就是用于区分不同对象的重要标识。无论对象自身的类型是什么，哈希值都是一个整数型。所以我们采用取模法实现

索引 = 哈希值 % 数组的长度 = index = HashCode % Array.length

不过JDK(Java Development Kit Java语言的软件开发工具包)中的哈希函数是采用位运算的方式实现，没有直接使用取模法。

通过哈希函数，我们可以把字符串或其他类型的Key,转化成数组的下标

例: 给定一个长度为8的数组 当key = 001121时

index = HashCode(“001121”,“张三”) % Array.length = 1420036703 % 8 = 7

哈希表的代码

哈希表=数组+链表

图解:

package com.philosophy7.hashtable;import java.util.Scanner;public class HashTableDemo {    public static void main(String[] args) { //1.创建一个哈希表 HashTable hashTable = new HashTable(7); //菜单 String key = ""; Scanner scanner = new Scanner(System.in); while (true) {     System.out.println("1." + "添加员工");     System.out.println("2." + "显示员工");     System.out.println("3." + "查找员工");     System.out.println("0." + "退出系统");     key = scanner.nextLine();     switch (key){  case "1":      System.out.println("输入id");      int id = scanner.nextInt();      System.out.println("请输入名字:");      String name = scanner.next();      //创建员工      Emp emp = new Emp(id,name);      hashTable.add(emp);      break;  case "2":      hashTable.list();      break;  case "3":      System.out.println("请输入要查找的id");      id = scanner.nextInt();      hashTable.findEmpById(id);      break;  case "0":      scanner.close();      System.exit(0);  default:      break;     } }    }}//员工类class Emp{    private int id;    private String name;    public Emp next; //为了更好的理解指针的操作 在这里我们用public修饰    public Emp(int id, String name) { super(); this.id = id; this.name = name;    }    public int getId() { return id;    }    public void setId(int id) { this.id = id;    }    public String getName() { return name;    }    public void setName(String name) { this.name = name;    }    @Override    public String toString() { return "Emp{" +  "id=" + id +  ", name='" + name + '\'' +  '}';    }}//创建EmpLinkedList链表class EmpLinkedList{    private Emp head; //头指针 指向的是第一个Emp 因此链表的头 是直接指向第一个Emp    //添加员工到列表 id是自增长    //也就是将员工直接添加到链表的尾部    public void add(Emp emp){ //若链表为空 if(head == null){     head = emp;     return; } //若链表不为空 -- 创建一个Emp节点(临时节点) 作用:更好的帮助我们进行插入操作 Emp curEmp = head; while (curEmp.next != null){     curEmp = curEmp.next; } //直到不进入循环 就证明该结点 == null 也就是说到了链表的最后一个结点 curEmp.next = emp; //于是将结点信息插入到尾部    }    //遍历链表    public void list(int no){ if (head == null){     System.out.println("第" +(no+1)+"条链表空");     return; } //不为空从头部开始遍历 Emp temp = this.head; System.out.print("第" +(no+1) +"条链表信息"); while (temp != null){     System.out.printf("=> id=%d name=%s\t",temp.getId(),temp.getName());     temp = temp.next; //指针往下移 }    }    //根据id查找雇员    //如果查找到 返回Emp 没有找到返回null    public Emp findEmpById(int id){ if (head == null){     System.out.println("链表为空");     return null; } //辅助指针 Emp temp = head; while (true){     if (temp.getId() == id){ //找到  break; //temp指向要查找到的员工     }     //退出 遍历到最后一个结点指向为Null 就表示啥也没找到     if (temp.next == null){  System.out.println("在哈希表中，没找到该员工");  temp = null;  break; //退出 不退出的话会报空指针异常     }     temp = temp.next; //往下找 } return temp;    }}//创建哈希表 用于管理多条链表class HashTable{    //数组 用于存放EmpLinkedList链表    private EmpLinkedList[] empLinkedListArray;    private int size; //统计链表的条数    public HashTable(int size){ //初始化数组的容量 this.size = size; //1.数组当中存放的是对象 所以默认初始化数据里面都是null 会造成空指针异常 empLinkedListArray = new EmpLinkedList[size]; //仅仅是创建了数组 //2.坑 这个时候需要初始化每条链表 否则将会报空指针异常 for (int i = 0; i < size; i++){     empLinkedListArray[i] =  new EmpLinkedList(); }    }    public void add(Emp emp){ //根据员工的id得到对应的信息,添加到哪条链表 int empLinkedListNo =  hashFunction(emp.getId()); //将emp添加到对应的链表中 empLinkedListArray[empLinkedListNo].add(emp);    }    //遍历所有链表    public void list(){ for (int i = 0; i < size; i++){     empLinkedListArray[i].list(i); }    }    //哈希函数 --- 采用取模法 当然不是魔法啦    public int hashFunction(int id){ return id % size;    }    //根据输入的id查找员工    public void findEmpById(int id){ //使用哈希函数确定到哪条链表 int  empLinkedNo = hashFunction(id); Emp emp = empLinkedListArray[empLinkedNo].findEmpById(id); if (emp != null){     System.out.println("在第"+(id+1)+"条链表找到了"); }else{     System.out.println("在哈希表没有找到该员工"); }    }}