哈希表 1、概念
存储键值对的数据结构
实现
数组 + 链表
数组 + 二叉树
2、应用场景
字典：
键：单词
值：释义（找出单词的释义）
图书索引：
键：术语
值：一串页码（找出相关的页码）
文件共享：
键：歌曲名
值：计算机ID（找到歌曲的下载地址）
账户管理：
键：账户号码
值：交易详情（处理交易）
网络搜索：
键：关键字
值：网页名称（找出相关网页）
编译器：
键：变量名
值：类型和值（找出符号的类型和值）
3、自定义哈希表
数组 + 链表
public class MyHashMap { // 存储链表的数组 private int size = 8; private LinkedList[] array = new LinkedList[size]; // 构造函数 public MyHashMap(){ for (int i = 0; i <size ; i++) { array[i] = new LinkedList(); } } // 结点 private static class Node{ int key; int value; Node next; public Node(int key) { this.key = key; } public Node(int key, int value) { this.key = key; this.value = value; } public Node(int key, int value, Node next) { this.key = key; this.value = value; this.next = next; } } // 链表 public static class LinkedList{ // 头结点 private Node head = null; // 添加结点 public void add(Node newNode){ // 如果head为空，说明此时该链表上没有元素，把新结点添加到头结点后 if (head == null){ head = newNode; } // 否则，把新结点添加到链表的最后一个元素上 else { // 遍历链表，找到最后一个元素 Node temp = head; while (temp.next != null){ temp = temp.next; } // 把新结点添加到最后一个结点上 temp.next = newNode; } } // 遍历链表 public void list(){ if (head == null){ System.out.println("空"); } Node temp = head; int index = 1; while (temp != null){ System.out.print("第" + index + "个结点：键为：" + temp.key + " 值为：" + temp.value); System.out.print("；"); temp = temp.next; index ++; } System.out.println(); } // 删除结点 public void delete(Node node){ if (head == null){ return; } // 如果头结点为要删除的结点 if (head == node){ head = node.next; return; } // 找到node结点的前一个结点 Node temp = head; while (temp.next != node){ temp = temp.next; } // 删除node结点 temp.next = node.next; node.next = null; } } // 哈希表存值 public void put(int key, int value) { int keyTemp = key % size; if(array[keyTemp].head == null){ array[keyTemp].add(new Node(key,value)); }else{ // 如果遍历链表的时候发现链表中有相同key，覆盖原值 Node temp = array[keyTemp].head; boolean flag = true; while (temp != null){ if (temp.key == key){ temp.value = value; flag = false; break; } temp = temp.next; } // 遍历结束，没有发现相同key，添加结点 if (flag){ array[keyTemp].add(new Node(key,value)); } } } // 遍历哈希表 public void list(){ for (int i = 0; i <size ; i++) { System.out.print("第" + (i + 1) + "条链表："); array[i].list(); } } // 哈希表取值 public int get(int key) { // 根据key值决定，在数组中的哪个链表中查找 int keyTemp = key % size; if (array[keyTemp].head == null){ return -1; }else{ Node temp = array[keyTemp].head; while (temp.key != key){ if (temp.next == null && temp.key != key){ return -1; } temp = temp.next; } return temp.value; } } // 哈希表删除值 public void remove(int key) { // 根据key确定在数组中的哪一个链表中删除元素 int keyTemp = key % size; // 如果链表中存在该键，删除键值对 // 遍历链表 Node temp = array[keyTemp].head; if (temp == null){ return; }else { while (temp != null){ if (temp.key == key){ array[keyTemp].delete(temp); break; } temp = temp.next; } } } }