数据结构学习——线性结构结构之哈希表

r囧r小猫 2023-09-28 14:27 156阅读 0赞

**目录**

一、哈希表的基本介绍

二、六种哈希函数 f(key) 的构造方法

1、直接定址法

2、数字分析法

3、平方取中法

4、折叠法

5、除留余数法

6、随机数法

除留余数示例

三、哈希查找（链表）

题目

解题思路

思路绘图

代码实现

四. 数据结构专栏

--------------------

### 一、哈希表的基本介绍 ###

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

### 二、六种哈希函数 f(key) 的构造方法 ###

#### 1、直接定址法 ####

> 哈希地址：f(key) = a\*key+b (a,b为常数)
> 
> 这种方法的优点是：简单，均匀，不会产生冲突。但是需要事先知道 key 的分布情况，适合查找表较小并且连续的情况。

例如：

![ca4549618bdce5bea5dd24a3bcb8780e.png][]

#### 2、数字分析法 ####

> 比如我们的11位手机号码“136xxxx5889”，其中前三位是接入号，一般对应不同运营公司的子品牌，如130是联通如意通，136是移动神州行等等。中间四位表示归属地。最后四位才是用户号。

> 若我们现在要存储某家公司员工登记表，如果用手机号码作为 key，那么极有可能前7位都是相同的，所以我们选择最后四位作为 f(key) 就是不错的选择。

#### 3、平方取中法 ####

> 故名思义，比如 key 是1234，那么它的平方就是1522756，再抽取中间的3位就是227作为 f(key) 。

#### 4、折叠法 ####

> 折叠法是将 key 从左到右分割成位数相等的几个部分(最后一部分位数不够可以短些)，然后将这几部分叠加求和，并按哈希表的表长，取后几位作为 f(key) 。

> 比如我们的 key 是 9876543210，哈希表的表长为3位，我们将 key 分为4组，987|654|321|0 ，然后将它们叠加求和 987+654+321+0=1962，再取后3位即得到 f(key) = 962 。

#### 5、除留余数法 ####

> 哈希地址：f(key) = key mod p (p<=m) m为哈希表表长。
> 
>  **这种方法是最常用的哈希函数构造方法。下面的代码中也使用了这种方法。**

**例如：**

> 如下图，创建一个0--15的数组，作为每个链表的头，将需要保存的数字进行模操作，根据结果放置在对应链表中。

例如：496%16=0，因此放在0开头的链表中

![a4338452a88b7045f012ed42a68375b0.png][]

#### 6、随机数法 ####

> 哈希地址：f(key) = random(key)
> 
> 这里 random 是随机函数，当 key 的长度不等时，采用这种方法比较合适。

> 例如负载均衡应用

#### 除留余数示例 ####

> 如下图所示，每来一个士兵都有一个六位的 hash 值（也可以称作编号），然后被用除以 3 取余数的方式分配到三个组。比如第一组中的编号为 123456 的士兵，除以 3 之后，整除，余数为 0，所以分配到第一组。

![81a329c49183b3817f40e8edbbb494d7.png][]

> 查找士兵

> 现在已经分好组了，假如想找到编号为 666666 的士兵该怎么找？首先将 666666 除以 3，得到余数 0，说明在第一个组，然后去第一个组里面找就可以了。

--------------------

### 三、哈希查找（链表） ###

#### 题目 ####

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

**要求：**

> 不使用数据库,尽量节省内存,速度越快越好=>哈希表(散列)

**思考：**

> 1、添加时，如何保证按照id从低到高插入
> 
> 2、如果id不是从低到高插入，但要求各条链表仍是从低到高，怎么解决？

#### 解题思路 ####

> 1、使用链表来实现哈希表, 该链表不带表头\[即: **链表的第一个结点就存放雇员信息**\]
> 
> 2、思路分析并画出示意图
> 
> 3、代码实现\[增删改查(显示所有员工，按id查询)\]

#### 思路绘图 ####

![3419e454818697f64b9c5e6c85013151.png][]

#### 代码实现 ####

import java.util.Scanner;
    
    //表示一个雇员节点
    class Emp {
    	public int id;
    	public String name;
    	public Emp next;
    
    	public Emp(int id, String name) {
    		this.id = id;
    		this.name = name;
    	}
    }
    
    //创建EmpLinkedList，表示哈希表中的某个链表
    class EmpLinkedList {
    	// 头指针，直接指向第一个Emp，默认null
    	private Emp head;
    
    	// 添加雇员到链表（直接添加到尾部）
    	public void add(Emp emp) {
    		if (head == null) { // 即添加第一个雇员
    			head = emp;
    			return;
    		}
    		// 如果不是第一个雇员，则遍历链表找到尾指针
    		Emp curEmp = head;
    		// 注意：因为头指针定义为指向第一个节点，所以不能使用while(curEmp.next!=null)
    		// 否则，当链表中只有一个节点时，第一次while(curEmp.next!=null)即为假
    		while (true) {
    			if (curEmp.next == null) {
    				break;
    			}
    			curEmp = curEmp.next;
    		}
    		// 退出时直接将emp 加入链表
    		curEmp.next = emp;
    	}
    
    	// 遍历链表的雇员信息
    	public void list(int no) {
    		if (head == null) { // 说明链表为空
    			System.out.println("第" + no + "链表为空");
    			return;
    		}
    		System.out.print("第" + no + "链表的信息为: ");
    		Emp curEmp = head; // 辅助指针
    		while (true) {
    			System.out.printf("=>id=%d;name=%s\t", curEmp.id, curEmp.name);
    			if (curEmp.next == null) {
    				break;
    			}
    			curEmp = curEmp.next;
    		}
    		System.out.println();
    	}
    
    	// 根据id查找雇员
    	public Emp findEmpById(int id) {
    		if (head == null) {
    			System.out.println("链表为空");
    			return null;
    		}
    		// 辅助指针
    		Emp curEmp = head;
    		while (true) {
    			if (curEmp.id == id) {
    				break;                // 这时curEmp就指向要查找的雇员
    			}
    			// 退出
    			if (curEmp.next == null) {// 说明遍历当前链表没有找到该雇员
    				curEmp = null;
    				break;
    			}
    			curEmp = curEmp.next;
    		}
    		return curEmp;
    	}
    }
    
    //创建哈希表， 管理多条链表
    class HashTab {
    	private EmpLinkedList[] empLinkedListArray;
    	private int size; // 表示有多少个链表
    
    	public HashTab(int size) {
    		this.size = size;
    		empLinkedListArray = new EmpLinkedList[size];
    		for (int i = 0; i < size; i++) {
    			empLinkedListArray[i] = new EmpLinkedList();
    		}
    	}
    
    	// 添加雇员
    	public void add(Emp emp) {
    		// 根据员工的id ,得到该员工应当添加到哪条链表
    		int empLinkedListNO = emp.id % size;
    		empLinkedListArray[empLinkedListNO].add(emp);
    	}
    
    	// 遍历所有的链表,遍历哈希表
    	public void list() {
    		for (int i = 0; i < size; i++) {
    			empLinkedListArray[i].list(i);
    		}
    	}
    
    	// 根据输入的id,查找雇员
    	public void findEmpById(int id) {
    		// 使用散列函数确定到哪条链表查找
    		int empLinkedListNO = id % size;
    		Emp emp = empLinkedListArray[empLinkedListNO].findEmpById(id);
    		if (emp != null) {// 找到
    			System.out.printf("在第%d条链表中找到雇员: id=%d, name=%s\n", empLinkedListNO, id, emp.name);
    		} else {
    			System.out.println("在哈希表中，没有找到该雇员~");
    		}
    	}
    }
    
    public class HashTabDemo {
    	public static void main(String[] args) {
    		Scanner scanner = new Scanner(System.in);
    		// 创建哈希表（设置哈希表长度，也就是哈希表中有几个链表）
    		HashTab hashTab = new HashTab(5);
    		int menu = 0;
    		while (menu != 4) {
    			System.out.println("------1:添加雇员---2:显示雇员---3:查找雇员---4:退出------");
    			menu = scanner.nextInt();
    			switch (menu) {
    			case 1:
    				System.out.println("请输入id");
    				int id = scanner.nextInt();
    				System.out.println("请输入名字");
    				String name = scanner.next();
    				hashTab.add(new Emp(id, name));
    				break;
    			case 2:
    				hashTab.list();
    				break;
    			case 3:
    				System.out.println("请输入要查找的id");
    				hashTab.findEmpById(scanner.nextInt());
    				break;
    			case 4:
    				System.out.println("------退出------");
    			default:
    				break;
    			}
    		}
    	}
    }

--------------------

### 四. 数据结构专栏 ###

[https://blog.csdn.net/weixin\_53919192/category\_11908333.html?spm=1001.2014.3001.5482![icon-default.png_t_M666][]https://blog.csdn.net/weixin\_53919192/category\_11908333.html?spm=1001.2014.3001.5482][https_blog.csdn.net_weixin_53919192_category_11908333.html_spm_1001.2014.3001.5482_icon-default.png_t_M666_https_blog.csdn.net_weixin_53919192_category_11908333.html_spm_1001.2014.3001.5482]

[ca4549618bdce5bea5dd24a3bcb8780e.png]: https://img-blog.csdnimg.cn/img_convert/ca4549618bdce5bea5dd24a3bcb8780e.png
[a4338452a88b7045f012ed42a68375b0.png]: https://img-blog.csdnimg.cn/img_convert/a4338452a88b7045f012ed42a68375b0.png
[81a329c49183b3817f40e8edbbb494d7.png]: https://img-blog.csdnimg.cn/img_convert/81a329c49183b3817f40e8edbbb494d7.png
[3419e454818697f64b9c5e6c85013151.png]: https://img-blog.csdnimg.cn/img_convert/3419e454818697f64b9c5e6c85013151.png
[icon-default.png_t_M666]: https://csdnimg.cn/release/blog_editor_html/release2.1.7/ckeditor/plugins/CsdnLink/icons/icon-default.png?t=M666
[https_blog.csdn.net_weixin_53919192_category_11908333.html_spm_1001.2014.3001.5482_icon-default.png_t_M666_https_blog.csdn.net_weixin_53919192_category_11908333.html_spm_1001.2014.3001.5482]: https://blog.csdn.net/weixin_53919192/category_11908333.html?spm=1001.2014.3001.5482