09_哈希表

哈希表概述

我们平常使用HashMap的时候假如有多多了解原码就知道，HashMap其实底层就是使用的数组+链表/红黑树的形式，那么这种形式其实就叫做哈希表，也叫做散列表

英文叫做HashTable，没错，也就是我们集合中的HashTable

那么哈希表到底是个什么东西呢？哈希表其实是一种查询效率非常快的数据结构，我们甚至可以用它来做缓存来减轻数据库的压力负担。

比如我们要插入某个值的时候，首先要对key进行一次运算，比如取余运算，得出这个值应该被放到哪个数组中，然后去判断数组，假如数组中没有值，那么可以直接进行插入，假如数组下方有值，那么我们可以选择链表形式的插入，或者是树形式的插入。

在我们取值的时候，还是要经过一次key的运算来得到应该在哪个数组中取得值，然后获得链表/树上的值，这样一来一回，节省的时间可不只是一点。

比如说，它就是下面这种形式：

---

哈希表的简单实现

现在有一个场景：公司里面有很多雇员，我们要实现对雇员的增删改查，但是不能使用数据库，并且要查询地足够快。

这个时候我们可以采用哈希表的实现方式。

要实现这个，可以有多个部分：

1、雇员的类，要有雇员号，姓名，住址等等

2、哈希表，要有节点链表的数组，要有头指针指向的链表的地址

3、哈希表的链表节点，要有data域，要有next域指向下一个节点

//链表节点
class Emp {
	public int id;
	public String name;
    //next节点默认为null
	public Emp next;
    
	public Emp(int id, String name) {
		super();
		this.id = id;
		this.name = name;
	}
}

//链表
class EmpLinkedList {
	//EMP,链表的头指针默认为null
	private Emp head;
	
	public void add(Emp emp) {
		if(head == null) {
			head = emp;
			return;
		}
		//定义一个临时节点，用于遍历整个链表
		Emp curEmp = head;
		while(true) {
            //找到链表的最后一个节点，我们向链表的最后插入
			if(curEmp.next == null) {
				break;
			}
			curEmp = curEmp.next;
		}
        //如果不是最后一个节点，那么继续寻找下一个节点，直到找到最后一个节点
		curEmp.next = emp;
	}
	
	//遍历链表
	public void list(int no) {
		if(head == null) {
			return;
		}
		//定义一个临时节点
		Emp curEmp = head;
		while(true) {
			System.out.printf(" => id=%d name=%s	", curEmp.id, curEmp.name);
			if(curEmp.next == null) {
				break;
			}
			curEmp = curEmp.next;
		}
		System.out.println();
	}

    //根据员工的ID号寻找对应的员工
	public Emp findEmpById(int id) {

		if(head == null) {
			return null;
		}
		//临时节点，遍历链表
		Emp curEmp = head;
		while(true) {
			if(curEmp.id == id) {
				break;
			}
			
			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) {
		//取余，这里模拟的是进行哈希算法得出来的下标，应该将节点插入到哪个数组索引下
		int empLinkedListNO = hashFun(emp.id);

		empLinkedListArray[empLinkedListNO].add(emp);
		
	}

	public void list() {
		for(int i = 0; i < size; i++) {
			empLinkedListArray[i].list(i);
		}
	}
	

	public void findEmpById(int id) {
		//取余，这里模拟的是进行哈希算法得出来的下标，应该将节点插入到哪个数组索引下
		int empLinkedListNO = hashFun(id);
		Emp emp = empLinkedListArray[empLinkedListNO].findEmpById(id);
		if(emp != null) {
			System.out.println(emp);
		}else{
			System.out.println("查询不到");
		}
	}
	
    //取余，这里模拟的是进行哈希算法得出来的下标，应该将节点插入到哪个数组索引下
	public int hashFun(int id) {
		return id % size;
	}
}

public class HashTabDemo {

	public static void main(String[] args) {
		

		HashTab hashTab = new HashTab(7);
		

		String key = "";
		Scanner scanner = new Scanner(System.in);
		while(true) {
			System.out.println("add:  添加");
			System.out.println("list: 遍历");
			System.out.println("find: 查找");
			System.out.println("exit: 退出");
			
			key = scanner.next();
			switch (key) {
			case "add":
				System.out.println("请输入id");
				int id = scanner.nextInt();
				System.out.println("请输入name");
				String name = scanner.next();
				Emp emp = new Emp(id, name);
				hashTab.add(emp);
				break;
			case "list":
				hashTab.list();
				break;
			case "find":
				System.out.println("请输入id");
				id = scanner.nextInt();
				hashTab.findEmpById(id);
				break;
			case "exit":
				scanner.close();
				System.exit(0);
			default:
				break;
			}
		}
	}
}