公众号merlinsea
- 背景
- 查找算法不论是顺序查找还是二分查找，其查找的过程中都需要进行若干次的比较，比如顺序查找需要经过n次的比较，二分查找需要经过logn次的比较，那么有没有什么数据结构可以保证1次比较或者只需要几次比较就可以判断是否能找到这样的元素呢？这种数据结构就是hash表。
- 什么是哈希表
- 哈希表又称为散列表，它是一种以键值对形式来存储数据的结构，只要输入待查找的key，就可以通过该key寻找到对应的值。
- 哈希表用的是数据支持下标随机访问数据的特性来实现的，所以说哈希表是数组的扩展，是由数据演化而成。
- 哈希表的新增操作
- 可以通过mod运算来算出数据应该存放到哈希表的哪个位置
- 比如key=19，value=40，hash表的表长是length=13，那么key % length = 6 ，因此key=19这个元素应该放在哈希表下标为6的位置。
- 哈希表的查找操作
- 对于给定的key通过mod运算找出对应的位置，然后判断再这个位置上是否有元素，即可以判断是否找到对应的元素。
- 哈希冲突
- 在我们对哈希表执行新增操作的时候，如果有多个元素映射到同一个哈希表中的位置，那么就产生了哈希冲突，也称之为哈希碰撞。
- 比如在上图的哈希表中，我们再新增元素key=89，value=89，此时我们计算出映射下标idx = 1 ，但之前的idx=1的位置已经存放了key=12的元素，这时就产生了哈希冲突。
- 哈希冲突解决方法
- 线性探测法：当发生冲突以后，就顺次向后挪动，直到找到第一个没有冲突的位置就停止下来。
- 二次探测法：当发生冲突以后，按照先右后左的顺序摆动，直到找到第一个没有冲突的位置就停止下来。
- 链地址法：基于链表的操作，来解决冲突问题， 当发生冲突以后，则把元素以链表的方法链接在对应的位置下面即可解决哈希冲突。
- 哈希表在有哈希冲突下的查询操作
- 首先我们需要计算出待查询元素位于哈希表的下标idx，如果下标idx元素为空，那么就认为找不到该元素
- 如果idx处不为空且结果不等于我们待查找的元素，应该按照哈希冲突的方法不断的挪动待查找的位置，直到找到元素或者遇到了第一个为空的位置就认为找不到元素。
- 哈希表在有哈希冲突下的删除操作
- 针对链地址法的哈希表，直接物理删除即可，因为物理删除不会引发歧义。
- 针对线性探测的哈希表和二次探测的哈希表，只能进行逻辑删除，即删除的时候做一个逻辑标记即可。如果直接物理删除，那么可能会导致后面待查询的元素明明在哈希表中，但却出现查询不到的情况。
- 评价哈希算法的指标
- 装载因子： 实际存储的空间 / 总存储空间
- 比如上图中装载因子 = 5 / 11 = 0.456,装载因子越大越容易发生哈希冲突。
- 手写实现一个以链表法解决冲突的哈希表
- 需要注意的点：
- 1、当实际装载的哈希槽超过了最大装载因子的容量需要考虑hash扩容
- 2、当同一个槽中产生的hash冲突超过一定数量的时候，需要考虑链表转为红黑树
- 3、哈希表的遍历时候，考虑实现一个迭代器
- 定义链表的节点
public class Node { private String key; private String value; private int hash; private Node next; public Node(String key, String value, int hash, Node next) { this.key = key; this.value = value; this.hash = hash; this.next = next; } public Node() { } public void setValue(String val){ this.value = val; } public String getKey(){ return key; } public Node getNext(){ return next; } public void setNext(Node next){ this.next = next; } @Override public boolean equals(Object o) { if (this == o) { return true; } if (!(o instanceof Node)){ return false; } Node node = (Node) o; return Objects.equals(key, node.key); } @Override public int hashCode() { return Objects.hash(key); } @Override public String toString() { return "Node{" + "key='" + key + '\'' + ", value='" + value + '\'' + ", hash=" + hash + '}'; } }
- 定义哈希表
public class MyHashTable { private Node[] table; private double loadFactor; private int size; private int availableBucket; // static 表示成员变量属于这个类 private static final double default_load_factor = 0.75; private static final int default_capacity = 16; private static final int linkToTreeCount = 8; public MyHashTable(int capacity,double loadFactor){ this.loadFactor = loadFactor; table = new Node[capacity]; size = 0; availableBucket = 0; } public MyHashTable(){ this(default_capacity,default_load_factor); } private int hash(String key){ return Objects.hash(key); } public void output(){ for(int i =0;i<table.length;i++){ Node p = table[i]; System.out.println("第 "+i+" 桶"); while(p!=null){ System.out.printf("%s\t",p.toString()); p = p.getNext(); } System.out.println(); } } public Node get(String key){ int hash = hash(key); int idx = (table.length-1)&hash; Node p = table[idx]; while(p!=null && !p.getKey().equals(key)){ p = p.getNext(); } return p; } public boolean put(String key,String value){ int hash = hash(key); int idx = (table.length-1)&hash; // if(table[idx] instanceof Node){ // // }else{ // // 红黑树插入 // } Node head = table[idx]; if(head == null){ table[idx] = new Node(key,value,hash,null); size++; availableBucket++; }else{ Node p = head; Node tar = new Node(key,value,hash,null); Node tail = null; int linkLen = 0; while(p!=null){ if(p.equals(tar)){ // 进行一个替换 p.setValue(value); return false; } tail = p; p = p.getNext(); linkLen++; } if(p==null){ tail.setNext(tar); linkLen++; } if(linkLen > linkToTreeCount){ // 链表转红黑树 // link2tree(); } } if(availableBucket >= (int)table.length*loadFactor){ // 扩容 // reszie(); } return true; } }
- Main函数调用
public class Main { public static void main(String[] args) { MyHashTable table = new MyHashTable(); table.put("123","1234"); table.put("1234","12345"); table.put("12","123"); table.put("1","12"); table.put("1235","123456"); table.put("123456","1234567"); table.put("123","321"); table.output(); System.out.println("get(123) = " +table.get("123")); } }
