JavaHashtable涉及的数据结构、实现及冲突处理

为什么80%的码农都做不了架构师&＃xff1f;>>>

Hashtable 提供的功能

Hashtable是一个线程安全的Map&＃xff0c;其线程安全是通过在各个方法上加上synchronized关键字实现的&＃xff0c;即&＃xff1a;该类只能被一个线程所使用&＃xff0c;其他调用该类时会阻塞等待;
实现了哈希表&＃xff0c;映射key到value&＃xff1b;
key和value都不能为null&＃xff0c;key类型必须实现hashCode()和equals()方法&＃xff1b;
put(K k,V v);
get(K k,V v);
~~Hashtable没有实现hash冲突的解决方案&＃xff0c;冲突需要按自己的逻辑实现&＃xff0c;它只提供了哈希表自动扩容的功能&＃xff1b;~~
出现hash冲突时&＃xff0c;采用单向链表来储存冲突的元素。

Hashtable 涉及到的概念

初始化容量&＃xff1a;key数组初始长度&＃xff0c;默认值是11
负载系数&＃xff08;load factor&＃xff09;&＃xff1a;即到达容量的百分比时&＃xff0c;哈希表就会重新hash到一个新容量的哈希表中,取值范围是&＃xff1a;<1.0 的百分数默认取值是.75(75%&＃xff0c;当加入的键值对数量达到初始容量的75%时&＃xff0c;继续加入的话会重新hash到一个新的容量的哈希表中)
阈(yù)值&＃xff1a;threshold&＃61;初始化容量*0.75和Integer.MAX_VALUE-8&＃xff08;注&＃xff1a;Integer.MAX_VALUE&＃61;0x7FFFFFFF&＃xff09; 中较小值
重新Hash&＃xff1a;加入元素时&＃xff0c;当数组大小大于等于阈值时&＃xff0c;key数组的容量会左移2位后&＃43;1即&＃xff1a;原容量*4&＃43;1&＃xff0c;然后按新的容量hash后放入新的数组中。
哈希函数&＃xff1a;(key.hashCode() & 0x7FFFFFFF) % key数组现在的长度

Hashtable常用方法分析

put(K k,V v); 添加元素到哈希表时&＃xff0c;判断元素是否存在&＃xff0c;如果存在&＃xff08;key的hash相同并且值也相同&＃xff09;的话&＃xff0c;就会覆盖掉原来的元素&＃xff0c;并返回原来的值&＃xff1b;如果不存在的话&＃xff0c;就会直接新建一个元素&＃xff0c;若产生hash冲突则将旧元素链接到新元素的尾部。
get(K k); 获取元素时&＃xff0c;先根据key的hash获取到对应key数组的下标&＃xff0c;获取对应的元素&＃xff08;因为数组元素的值是一个单链表&＃xff0c;所以如果当前的值不匹配时就需要判断链表的下一个元素&＃xff09;。

处理 Hash冲突

Hashtable 处理 Hash冲突时通过单链表。。

涉及的基本概念

位运算
数组
哈希表
单链表
Java transient 关键字原理
Java 序列化、反序列化以及自定义序列化、反序列话逻辑&＃xff08;writeObject(ObjectOutputStream o)和readObject(ObjectInputStream i)&＃xff09;

存在未理解之处

Hashtable的count字段是什么时候初始化的&＃xff1f;从赋值来看是通过readObject()方法来实现的。但是具体实现需要回去取研读下《Java编程思想》序列化章节内容。

private transient int count; 未理解之处的解答

Hashtable的count字段是什么时候初始化的&＃xff1f;因为该变量是类变量编译的时候会自动赋值。可以总结下Java各种类型的变量。

模拟hash冲突

可以根据hash函数(key.hashCode() & 0x7FFFFFFF) % key数组现在的长度来模拟hash冲突&＃xff0c;只要key的hashCode是相同但是又不equals()的就是Hash冲突。如下实例&＃xff1a;

public class MyKey implements Serializable {private int i;public MyKey(int i) {this.i &＃61; i;}[&＃64;Override](https://my.oschina.net/u/1162528)public int hashCode() {if (i % 2 &＃61;&＃61; 0) {return 1;} else {return 2;}}} Hashtable处理hash冲突

如下实例&＃xff1a;

public static void main(String[] args) {Hashtable map &＃61; new Hashtable<>();for (int i &＃61; 0; i <11; i&＃43;&＃43;) {map.put(new MyKey(i), i);}map.get(new MyKey(1)); } 如何在IDEA调试模式下查看储存结构&＃xff1f;

Hashtable在IDEA下的默认视图&＃xff1a;

Java-Hashtable-data-structure-default-view

如何查看对象视图&＃xff1f;如下图操作&＃xff1a;

Java-Hashtable-data-structure

对象视图如下

Java-Hashtable-data-structure-object-view

从如上对象视图可以看出Hashtable的table字段的具体存储方式&＃xff1a; table数组中有两个元素&＃xff0c;一个是MyKey.i&＃61;10&＃xff0c;一个是Mykey.i&＃61;9,按如上查看对象视图的方法查看这两个元素的对象视图查看java.util.Hashtable.Entry#next属性&＃xff0c;可以看到MyKey.i&＃61;10的next属性值是MyKey.i&＃61;8... 各元素的具体结构如下&＃xff1a;

MyKey.i&＃61;10.next -> MyKey.i&＃61;8 MyKey.i&＃61;8.next -> MyKey.i&＃61;0 MyKey.i&＃61;0.next -> MyKey.i&＃61;2 MyKey.i&＃61;2.next -> MyKey.i&＃61;4 MyKey.i&＃61;4.next -> MyKey.i&＃61;6 MyKey.i&＃61;6.next -> nullMyKey.i&＃61;9.next -> MyKey.i&＃61;1 MyKey.i&＃61;1.next -> MyKey.i&＃61;3 MyKey.i&＃61;3.next -> MyKey.i&＃61;5 MyKey.i&＃61;5.next -> MyKey.i&＃61;7 MyKey.i&＃61;7.next -> null

为什么顺序不是按加入的顺序的呢&＃xff0c;而是一部分到过来的&＃xff1f;
因为Hashtable的key数组默认大小是11&＃xff0c;当加入11个元素时&＃xff0c;会自动扩容&＃xff0c;在加入第8个元素时会rehash一次&＃xff0c;rehash时是将新哈希表中的元素作为后面加入元素的next的&＃xff0c;所有就会出现部分元素顺序相反。