集合学习--HashTable 源码初探

时间：2023-02-24 17:51:59

HashTable

装填因子的定义

α=表中填入的记录数哈希表的长度

线性探测再散列的哈希表查找成功时的成功查找长度

Snl≈12(1+11−α)

随机探测在再散列丶二次探测再散列丶再哈希的哈希表查找成功时的平均查找长度为

Snr≈−1αln(1−α)

链地址法处理冲突的哈希表查找成功时的平均查找长度为

Snc≈α2+1

由上可见查找长度与 α 有关

而在HashTable 的构造方法就是HashMap

 /**
 * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
 * default initial capacity (16) and load factor (0.75).
 */
public HashSet() {
        map = new HashMap<>();
    }

由上可知装填因子默认为0.75
默认平均查找长度为1.375

HashMap与HashTable的不同

  1. 我们从他们的定义就可以看出他们的不同，HashTable 基于 Dictionary 类，而 HashMap 是基于 AbstractMap。Dictionary 是什么？它是任何可将键映射到相应值的类的抽象父类（已过时 ，从Java 2 平台 v1.2起，此类就被改进以实现 Map 接口，使它成为 Java Collections Framework 中的一个成员。不像新的 collection 实现，Hashtable 是同步的

），而 AbstractMap 是基于 Map 接口的骨干实现，它以最大限度地减少实现此接口所需的工作。
2. Hashtable 的方法是同步的，而 HashMap 的方法不是。如果多个线程同时访问一个哈希映射，而其中至少一个线程从结构上修改了该映射，则它必须 保持外部同步。（结构上的修改是指添加或删除一个或多个映射关系的任何操作；仅改变与实例已经包含的键关联的值不是结构上的修改。）这一般通过对自然封装该映射的对象进行同步操作来完成。如果不存在这样的对象，则应该使用 Collections.synchronizedMap 方法来“包装”该映射。最好在创建时完成这一操作，以防止对映射进行意外的非同步访问，如下所示：

Map m = Collections.synchronizedMap(new HashMap(…));
3. HashMap 可以允许存在一个为 null 的 key 和任意个为 null 的 value，但是 HashTable 中的 key 和 value 都不允许为 null。如下：

//当 HashMap 遇到为 null 的 key 时，它会调用 putForNullKey 方法来进行处理。对于 value 没有进行任何处理，只要是对象都可以。
if (key == null)
return putForNullKey(value);
// 而当 HashTable 遇到 null 时，他会直接抛出 NullPointerException异常信息。
if (value == null) {
throw new NullPointerException();
}
标签：

相关文章