Java面试知识点（一）hashmap、hashtable和hashset

1. 关于 HashMap 的一些说法：

a) HashMap 实际上是一个 “链表散列” 的数据结构，即数组和链表的结合体。HashMap 的底层结构是一个数组，数组中的每一项是一条链表。

b) HashMap 的实例有俩个参数影响其性能： “初始容量” 和 装填因子。

c) HashMap 实现不同步，线程不安全。 HashTable 线程安全

d) HashMap 中的 key-value 都是存储在 Entry 中的。

e) HashMap 可以存 null 键和 null 值，不保证元素的顺序恒久不变，它的底层使用的是数组和链表，通过 hashCode () 方法和 equals 方法保证键的唯一性

f) 解决冲突主要有三种方法：定址法，拉链法，再散列法。HashMap 是采用拉链法解决哈希冲突的。

注：
链表法是将相同 hash 值的对象组成一个链表放在 hash 值对应的槽位；

用开放定址法解决冲突的做法是：当冲突发生时，使用某种探查 (亦称探测) 技术在散列表中形成一个探查 (测) 序列。 沿此序列逐个单元地查找，直到找到给定 的关键字，或者碰到一个开放的地址 (即该地址单元为空) 为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。

拉链法解决冲突的做法是： 将所有关键字为同义词的结点链接在同一个单链表中 。若选定的散列表长度为 m，则可将散列表定义为一个由 m 个头指针组成的指针数 组 T [0…m-1]。凡是散列地址为 i 的结点，均插入到以 T [i] 为头指针的单链表中。T 中各分量的初值均应为空指针。在拉链法中，装填因子 α 可以大于 1，但一般均取 α≤1。拉链法适合未规定元素的大小。

2. Hashtable 和 HashMap 的区别：

HashMap 是 Hashtable 的轻量级实现（非线程安全的实现），他们都完成了 Map 接口。主要的区别有：线程安全性，同步 (synchronization)，以及速度。

a) 继承不同。

public class Hashtable extends Dictionary implements Map

public class HashMap extends AbstractMap implements Map

b) Hashtable 中的方法是同步的，而 HashMap 中的方法在缺省情况下是非同步的。在多线程并发的环境下，可以直接使用 Hashtable，但是要使用 HashMap 的话就要自己增加同步处理了。

c) Hashtable 中， key 和 value 都不允许出现 null 值。 在 HashMap 中， null 可以作为键，这样的键只有一个；可以有一个或多个键所对应的值为 null 。当 get() 方法返回 null 值时，即可以表示 HashMap 中没有该键，也可以表示该键所对应的值为 null 。因此，在 HashMap 中不能由 get() 方法来判断 HashMap 中是否存在某个键， 而应该用 containsKey() 方法来判断。

d) 两个遍历方式的内部实现上不同。Hashtable、HashMap 都使用了 Iterator。而由于历史原因，Hashtable 还使用了 Enumeration 的方式 。

e) 哈希值的使用不同，HashTable 直接使用对象的 hashCode。而 HashMap 重新计算 hash 值。

f) Hashtable 和 HashMap 它们两个内部实现方式的数组的初始大小和扩容的方式。HashTable 中 hash 数组默认大小是 11，增加的方式是 old*2+1。HashMap 中 hash 数组的默认大小是 16，而且一定是 2 的指数。

注： HashSet 子类依靠 hashCode () 和 equal () 方法来区分重复元素。

HashSet 内部使用 Map 保存数据，即将 HashSet 的数据作为 Map 的 key 值保存，这也是 HashSet 中元素不能重复的原因。而 Map 中保存 key 值的，会去判断当前 Map 中是否含有该 Key 对象，内部是先通过 key 的 hashCode, 确定有相同的 hashCode 之后，再通过 equals 方法判断是否相同。

3. hashmap和hashtable源码分析

//HashMap的源码
public class HashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable

//Hashtable的源码