Java数据结构篇五：Hashtable

前言

HashTable：（1）不允许null键null值  （2）线程安全 
（3）Hashtable默认的初始大小为11，之后每次扩充，容量变为原来的2n+1

第1部分 介绍

简介

和一样， 也是一个散列表，它存储的内容是键值对(key-value)映射。

继承于，实现了Map、、java.io.接口。

的函数都是同步的，这意味着它是线程安全的。它的key、value都不可以为null。此外，中的映射不是有序的。

的实例有两个参数影响其性能：初始容量和加载因子。容量 是哈希表中桶 的数量，初始容量 就是哈希表创建时的容量。注意，哈希表的状态为 open：在发生“哈希冲突”的情况下，单个桶会存储多个条目，这些条目必须按顺序搜索。加载因子 是对哈希表在其容量自动增加之前可以达到多满的一个尺度。初始容量和加载因子这两个参数只是对该实现的提示。关于何时以及是否调用 方法的具体细节则依赖于该实现。

通常，默认加载因子是 0.75, 这是在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查找某个条目的时间（在大多数 操作中，包括 get 和 put 操作，都反映了这一点）。

的构造函数

// 默认构造函数。
public Hashtable() // 指定“容量大小”的构造函数
public Hashtable(int initialCapacity) // 指定“容量大小”和“加载因子”的构造函数
public Hashtable(int initialCapacity, float loadFactor) // 包含“子Map”的构造函数
public Hashtable(Map t)

的API

synchronized void                clear()
synchronized Object              clone()boolean             contains(Object value)
synchronized boolean             containsKey(Object key)
synchronized boolean             containsValue(Object value)
synchronized Enumeration      elements()
synchronized Set>    entrySet()
synchronized boolean             equals(Object object)
synchronized V                   get(Object key)
synchronized int                 hashCode()
synchronized boolean             isEmpty()
synchronized Set              keySet()
synchronized Enumeration      keys()
synchronized V                   put(K key, V value)
synchronized void                putAll(Map map)
synchronized V                   remove(Object key)
synchronized int                 size()
synchronized String              toString()
synchronized Collection       values()

第2部分 数据结构

的继承关系

java.lang.Object↳     java.util.Dictionary↳     java.util.Hashtablepublic class Hashtable extends Dictionaryimplements Map, Cloneable, java.io.Serializable { }

与Map关系如下图：

基本数据结构

从图中可以看出：

(01) 继承于类，实现了Map接口。Map是"key-value键值对"接口，是声明了操作"键值对"函数接口的抽象类。

(02) 是通过"拉链法"实现的哈希表。它包括几个重要的成员变量：table,count,,,。

table是一个Entry[]数组类型，而Entry实际上就是一个单向链表。哈希表的"key-value键值对"都是存储在Entry数组中的。

count是的大小，它是保存的键值对的数量。

是的阈值，用于判断是否需要调整的容量。的值="容量*加载因子"。

就是加载因子。

是用来实现fail-fast机制的

源码分析详见：