我们知道，HashMap和HashTable都是基于哈希表完成的，那我们首先来回顾哈希表的知识。
散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。 给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。
许多缓存技术（比如memcached）的核心其实就是在内存中维护一张大的哈希表。
数据的物理存储结构：顺序存储 + 链式存储 我们先大概了解下其他数据结构在增、删、查等基础操作执行性能。
数据结构增删查数组采用一段连续的存储单元来存储数据一般的插入删除操作，涉及到数组元素的移动，其平均复杂度也为O(n)（1）指定下标的查找，时间复杂度为O(1) （2）给定值进行查找，需要遍历数组，逐一比对给定关键字和数组元素，时间复杂度为O(n) （3）有序数组，则可采用二分查找，时间复杂度提高为O(logn)线性链表找到指定位置，处理结点间的引用，时间复杂度为O(1)遍历链表逐一比对，复杂度为O(n)找到指定位置，处理结点间的引用，时间复杂度为O(1)二叉树一棵相对平衡的有序二叉树，平均复杂度均为O(logn)一棵相对平衡的有序二叉树，平均复杂度均为O(logn)一棵相对平衡的有序二叉树，平均复杂度均为O(logn)哈希表不考虑哈希冲突，一次定位即可，时间复杂度为O(1)不考虑哈希冲突，一次定位即可，时间复杂度为O(1)不考虑哈希冲突，一次定位即可，时间复杂度为O(1)哈希表的主干就是数组，在数组中根据下标查找某个元素，一次定位就可以找到。 新增或者查找某个元素时，我们把当前元素的关键字通过哈希函数映射到数组中的某个位置，通过数组下标一次定位就可完成。
哈希函数：存储位置 = f(关键字)
哈希冲突： 两个不同的元素，通过哈希函数得出的实际存储地址相同，这就叫哈希冲突（哈希碰撞）。 好的哈希函数会尽可能地保证计算简单和散列地址分布均匀。
如何解决哈希冲突？
开放定址法：一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入 。再散列函数法：有多个不同的Hash函数，当发生冲突时，使用第二个，第三个，….，等哈希函数计算地址，直到无冲突。虽然不易发生聚集，但是增加了计算时间。建立公共溢出区： 将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。链地址法：数组 + 链表，数组的每个元素都是一个链表，当两个元素哈希的值相同而发生冲突时，直接头插到当前链表中。（1）HashMap 是基于哈希表完成的，每一个元素是一个 key - value 对。 （2）HashMap 的数据结构是 数组 + 单链表 。数组为 HashMap 的主体，链表则是为了解决哈希冲突。 （3）HashMap 的数组初始化大小为 16， 负载因子为0.75，需要扩容使，扩容为原数组长度的二倍。
变量size，它记录HashMap的底层数组中已用槽的数量；变量threshold，它是HashMap的阈值，用于判断是否需要调整HashMap的容量（threshold = 容量*加载因子）；变量DEFAULT_LOAD_FACTOR = 0.75f，默认加载因子为0.75； 加载因子越大，对空间的利用更充分，但是查找效率会降低（链表长度会越来越长）；如果加载因子太小，那么表中的数据将过于稀疏（很多空间还没用，就开始扩容了），对空间造成严重浪费。HashMap扩容的条件是：当size大于threshold时，对HashMap进行扩容。 扩容是是新建了一个HashMap的底层数组，而后调用transfer方法，将就HashMap 的全部元素添加到新的HashMap中（要重新计算元素在新的数组中的索引位置）。 很明显，扩容是一个相当耗时的操作，因为它需要重新计算这些元素在新的数组中的位置并进行复制处理。因此，我们在用HashMap的时，最好能提前预估下HashMap中元素的个数，这样有助于提高HashMap的性能。（4）hash 过程，确定最终存储位置： key --------> hashcode --------> h --------> 存储下标
key 经过 hashCode() 得到 hashcodehashcode 经过一系列位运算得到 hh 经过 indexFor() 得到存储下标当准备添加一个key-value对时，首先通过hash(key)方法计算hash值，然后通过indexFor(hash,length)求该key-value对的存储位置，计算方法是先用hash&0x7FFFFFFF后，再对length取模，这就保证每一个key-value对都能存入HashMap中，当计算出的位置相同时，由于存入位置是一个链表，则把这个key-value对 头插至链表。
（5）在重写 equals() 方法的同时，必须重写 hashCode() 方法，同时要保证通过 equals() 方法判断相等的两个对象，调用 hashCode() 方法也返回同样的值。 （6）在 jdk1.8 中，当链表长度超过8，链表转换为红黑树，利用红黑树快速增删查改的特点来提高 hashMap 的性能。 （7）HashMap是非线程安全的，只是用于单线程环境下，多线程环境下可以采用concurrent并发包下的concurrentHashMap。 （8）HashMap 实现了Serializable接口，因此它支持序列化，实现了Cloneable接口，能被克隆。
（1）Hashtable 是基于哈希表完成的，每一个元素是一个 key - value 对。 （2）Hashtable也是JDK1.0引入的类，是线程安全的，能用于多线程环境中。 （3）Hashtable同样实现了Serializable接口，它支持序列化，实现了Cloneable接口，能被克隆。
为什么 Hashtable 的 t 是小写呢？ Hashtable是在Java 1中创建的。集合的一致命名约定是后来在Java2中建立的，当时其他类作为全新的Java集合框架的一部分发布。 驼峰命名规则是 Hashtable 之后出现的，后来大量的 Java程序都使用了Hashtable 这个类，因此就无法修改Hashtable为HashTable了。
1. 继承的父类不同
HashMap继承自AbstractMap类。但二者都实现了Map接口。Hashtable继承自Dictionary类，Dictionary类是一个已经被废弃的类（见其源码中的注释）。父类都被废弃，自然而然也没人用它的子类Hashtable了。2. 线程安全与否
HashMap 线程不安全Hashtable 线程安全 javadoc中关于hashmap的一段描述如下：此实现不是同步的。如果多个线程同时访问一个哈希映射，而其中至少一个线程从结构上修改了该映射，则它必须保持外部同步。Hashtable 中的方法大多是Synchronize的，而HashMap中的方法在一般情况下是非Synchronize的。在多线程并发的环境下，可以直接使用Hashtable，不需要自己为它的方法实现同步，但使用HashMap时就必须要自己增加同步处理。Hashtable实现线程安全的代价就是效率变低，因为会锁住整个HashTable,而ConcurrentHashMap做了相关优化,因为ConcurrentHashMap使用了分段锁，并不对整个数据进行锁定,效率比Hashtable高很多。3. 是否允许 null 值
HashMap 是允许key和value为null值的，用containsValue和containsKey方法判断是否包含对应键值对。Hashtable 键值对都不能为空，否则包空指针异常。4. 包含的contains方法不同
HashMap 把 Hashtable 的 contains() 方法去掉了，改成 containsValue() 和 containsKey() ，因为contains() 方法容易让人引起误解。Hashtable 则保留了 contains()，containsValue() 和 containsKey() 三个方法，其中 contains() 和 containsValue() 功能相同。5. 扩容方式不同（容量不够） 当容量不足时要进行resize方法，而resize的两个步骤： ① 扩容； ② rehash: HashMap 和 Hashtable 都会会重新计算 hash值。
HashMap 扩容为原容量的2倍，而且一定是2的幂次倍扩容结果，而且每次扩容时，原来数组中的元素依次重新计算存放位置，并重新插入；Hashtable扩容为原容量2倍加1；