Hashtable的结构,采用的是数据结构中所说的链地址法处理冲突的方法
从上面的结构图可以看出,Hashtable的实质就是一个数组+链表。图中的Entry就是链表的实现,Entry的结构中包含了对自己的另一个实例的引用next,用以指向另外一个Entry。而图中标有数字的部分是一个Entry数组,数字就是这个Entry数组的index。那么往Hashtable增加键值对的时候,index会根据键的hashcode、Entry数组的长度共同决定,从而决定键值对存放在Entry数组的哪个位置。从这种意义来说,当键一定,Entry数组的长度一定的情况下,所得到的index肯定是相同的,也就是说插入顺序应该不会影响输出的顺序才对。然而,还有一个重要的因素没有考虑,就是计算index出现相同值的情况。譬如代码中 "sichuan" 和 "anhui",所得到的index是相同的,在这个时候,Entry的链表功能就发挥作用了:put方法通过Entry的next属性获得对另外一个Entry的引用,然后将后来者放入其中。根据debug得出的结果,"sichuan", "anhui"的index同为2,"hunan"的index为6,"beijing"的index为1,在输出的时候,会以index递减的方式获得键值对。很明显,会改变的输出顺序只有"sichuan"和"anhui"了,也就是说输出只有两种可能:"hunan" - "sichuan" - "anhui" - "beijing"和"hunan" - "anhui" - "sichuan" - "beijing"。以下是运行了示例代码之后,Hashtable的结果:
在Hashtable的实现代码中,有一个名为rehash的方法用于扩充Hashtable的容量。很明显,当rehash方法被调用以后,每一个键值对相应的index也会改变,也就等于将键值对重新排序了。这也是往不同容量的Hashtable放入相同的键值对会输出不同的键值对序列的原因。在Java中,触发rehash方法的条件很简单:hahtable中的键值对超过某一阀值。默认情况下,该阀值等于hashtable中Entry数组的长度×0.75。
自 Java 2 平台 v1.2 以来,此类已经改进为可以实现 Map,因此它变成了 Java Collections Framework 的一部分。与新集合的实现不同,Hashtable 是同步的。
由迭代器返回的 Iterator 和由所有 Hashtable 的“collection 视图方法”返回的 Collection 的 listIterator 方法都是快速失败 的:在创建 Iterator 之后,如果从结构上对 Hashtable 进行修改,除非通过 Iterator 自身的移除或添加方法,否则在任何时间以任何方式对其进行修改,Iterator 都将抛出 ConcurrentModificationException。因此,面对并发的修改,Iterator 很快就会完全失败,而不冒在将来某个不确定的时间发生任意不确定行为的风险。由 Hashtable 的键和值方法返回的 Enumeration 不 是快速失败的。
注意,迭代器的快速失败行为无法得到保证,因为一般来说,不可能对是否出现不同步并发修改做出任何硬性保证。快速失败迭代器会尽最大努力抛出 ConcurrentModificationException。因此,为提高这类迭代器的正确性而编写一个依赖于此异常的程序是错误做法:迭代器的快速失败行为应该仅用于检测程序错误。
Hashtable中的Entry数据结构
put方法:key的hash值不同但是可能放入的index相同,并且在放入之前需要判断
2 return this.<K>getEnumeration(KEYS);
3 }
4
5 private <T> Enumeration<T> getEnumeration(int type) {
6 if (count == 0) {
7 return (Enumeration<T>)emptyEnumerator;
8 } else {
9 return new Enumerator<T>(type, false);
10 }
11 }
12
13 public synchronized Enumeration<V> elements() {
14 return this.<V>getEnumeration(VALUES);
15 }
16
17Enumerator是Hashtable定义的一个内部类
18 private class Enumerator<T> implements Enumeration<T>, Iterator<T> {
19 Entry[] table = Hashtable.this.table;//访问宿主类的成员变量
20 int index = table.length;
21 Entry<K,V> entry = null;
22 Entry<K,V> lastReturned = null;
23 int type;
24
25 /**
26 * Indicates whether this Enumerator is serving as an Iterator
27 * or an Enumeration. (true -> Iterator).
28 */
29 boolean iterator;
30
31 /**
32 * The modCount value that the iterator believes that the backing
33 * Hashtable should have. If this expectation is violated, the iterator
34 * has detected concurrent modification.
35 */
36 protected int expectedModCount = modCount;
37}
38内部类中提供了访问了hashtable中的entry数组的方法.
39在实现Iterator接口中的方法时使用了expectedModCount变量来判断是否有并发修改而导致fast-fail,而在Enumeration的接口方法实现中没有判断
40
41
42
43 public Set<K> keySet() {
44 if (keySet == null)
45 keySet = Collections.synchronizedSet(new KeySet(), this);
46 return keySet;
47 }
48 private class KeySet extends AbstractSet<K> {
49 public Iterator<K> iterator() {
50 return getIterator(KEYS);
51 }
52 public int size() {
53 return count;
54 }
55 public boolean contains(Object o) {
56 return containsKey(o);
57 }
58 public boolean remove(Object o) {
59 return Hashtable.this.remove(o) != null;
60 }
61 public void clear() {
62 Hashtable.this.clear();
63 }
64 }
65内部类KeySet中有iterator接口方法的实现,调用的宿主类的getIterator(KEYS)
66 private <T> Iterator<T> getIterator(int type) {
67 if (count == 0) {
68 return (Iterator<T>) emptyIterator;
69 } else {
70 return new Enumerator<T>(type, true);
71 }
72 }
73getIterator中new 了一个新的内部类Enumerator的对象,最终使用Enumerator来访问hashtable的entry数组,能不能在内部类中直接创建一个内部类的的实例???
74
75
76
77 public Collection<V> values() {
78 if (values==null)
79 values = Collections.synchronizedCollection(new ValueCollection(),
80 this);
81 return values;
82 }
83ValueCollection也是一个内部类,结构和KeySet功能差不多
84 public Set<Map.Entry<K,V>> entrySet() {
85 if (entrySet==null)
86 entrySet = Collections.synchronizedSet(new EntrySet(), this);
87 return entrySet;
88 }
89EntrySet也是内部类,结构和KeySet功能差不多
相关推荐
《实战应用Java算法分析与设计(链表、二叉树、哈夫曼树、图、动态规划、HashTable算法)》 课程简介: 算法分析与设计Java版,是一套实用型算法课程。通过本课程的学习,学员可以掌握以下技术点:线性结构与顺序表...
Hashtable的应用非常广泛,HashMap是新框架中用来代替Hashtable的类,也就是说建议使用HashMap,不要使用Hashtable。可能你觉得Hashtable很好用,为什么不用呢?这里简单分析他们的区别。
在上一篇博客 Java容器之HashMap源码分析(妈妈再也不用担心我不懂HashMap了) 从源码层次分析了HashMap容器的底层实现,在本篇博客将继续从源码层次分析Hashtable的底层实现。 注明:以下源码分析都是基于jdk ...
以下是对java中的hashtable进行了详细的分析介绍。需要的朋友可以过来参考下
《实战应用Java算法分析与设计(链表、二叉树、哈夫曼树、图、动态规划、HashTable算法)》 算法分析与设计Java版,是一套实用型算法课程。通过本课程的学习,学员可以掌握以下技术点:线性结构与顺序表、单向链表、...
java中Hashtable和HashMap的区别分析,需要的朋友可以参考一下
│ Java面试题11.HashMap和HashTable的区别.mp4 │ Java面试题12.实现一个拷贝文件的类使用字节流还是字符串.mp4 │ Java面试题13.线程的实现方式 怎么启动线程怎么区分线程.mp4 │ Java面试题14.线程并发库和线程池...
算法分析与设计课的PPT 算法:是指解决问题的一种方法或一个过程,在计算机领域是指满足下述性质的指令序列。(1)输入:有外部提供的量作为算法的输入。 (2)输出:算法产生至少一个量作为输出。 (3)确定性:组成算法...
以下是对Java中HashMap和Hashtable及HashSet的区别进行了详细的分析介绍,需要的朋友可以过来参考下
本书不仅全面的介绍了Java语言本身,最重要还交会读者去掌握编程思想,找到编程感觉,而不是死记硬背语言本身,书中涉及到的应用问题分析,远远超了一个Java程序员在学习和应用Java过程中所有可能碰到的问题。...
javascript里面是没有哈希表的,一直在java,C#中有时候用到了这一种数据结构,javascript里面若没有,感觉非常不顺手。细细看来,其实javascript的object的属性其实与哈希表非常类似。 如: var person = {}; person[...
7.6.1 HashMap和Hashtable实现类 271 7.6.2 SortedMap接口和TreeMap实现类 276 7.6.3 WeakHashMap实现类 279 7.6.4 IdentityHashMap实现类 280 7.6.5 EnumMap实现类 281 7.7 HashSet和HashMap的性能选项 282 ...
1.12 分析和设计 1.12.1 不要迷失 1.12.2 阶段0:拟出一个计划 1.12.3 阶段1:要制作什么? 1.12.4 阶段2:开始构建? 1.12.5 阶段3:正式创建 1.12.6 阶段4:校订 1.12.7 计划的回报 1.13 Java还是C++? 第2章 ...
1.12 分析和设计 1.12.1 不要迷失 1.12.2 阶段0:拟出一个计划 1.12.3 阶段1:要制作什么? 1.12.4 阶段2:开始构建? 1.12.5 阶段3:正式创建 1.12.6 阶段4:校订 1.12.7 计划的回报 1.13 Java还是C++? 第2章 ...
1.12 分析和设计 1.12.1 不要迷失 1.12.2 阶段0:拟出一个计划 1.12.3 阶段1:要制作什么? 1.12.4 阶段2:开始构建? 1.12.5 阶段3:正式创建 1.12.6 阶段4:校订 1.12.7 计划的回报 1.13 Java还是C++? 第2章 ...
1.12 分析和设计 1.12.1 不要迷失 1.12.2 阶段0:拟出一个计划 1.12.3 阶段1:要制作什么? 1.12.4 阶段2:开始构建? 1.12.5 阶段3:正式创建 1.12.6 阶段4:校订 1.12.7 计划的回报 1.13 Java还是C++? 第2章 ...
Hashtable是怎么加锁的。 HashMap的并发问题。 ConcurrenHashMap 介绍。 AQS。 如何检测死锁,怎么预防死锁。 Java内存模型。 线程池的种类,区别和使用场景。 分析线程池的实现原理和线程的调度过程。 线程池如何...
1.12 分析和设计 1.12.1 不要迷失 1.12.2 阶段0:拟出一个计划 1.12.3 阶段1:要制作什么? 1.12.4 阶段2:开始构建? 1.12.5 阶段3:正式创建 1.12.6 阶段4:校订 1.12.7 计划的回报 1.13 Java还是C++? 第2章 ...