HashMap与HashTable的实现原理与区别

[jingegebuguai]

实现原理

HashMap和HashTable都是通过数组和链表实现的。

增删改查操作都需要先计算hash值，根据hash和table.length计算出index的具体位置（table的下标），然后再进行相关操作。

HashMap初始化变量如下

//默认初始容量为16
static final int DEFAULT_INITIAL_CAPACITY = 16;
//HashMap最大容量
static final int MAXIMUM_CAPACITY = 1<<30;
//默认加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75;
//默认存储数据的数组
transient Entry[] table;

构造函数

HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    //设置临界阙值
    threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
    table = new Entry[DEFAULT_INITIAL_CAPACITY];
    init();
}

put和get方法原理：
HashMap先对为null值得key进行特殊处理，放到table[0]的位置。put是先计算hash值，再和table.length进行取模计算得到index，将key放到table[index]的位置。当table[index]已存在其它元素时，会在table[index]位置形成一个链表，将新添加的元素放在table[index]，原来的元素通过Entry的next进行链接，这样以链表形式解决hash冲突问题，当元素数量达到临界值(capactiyfactor)时，则进行扩容，是table数组长度变为table.length2。

区别

两者最主要的区别在于Hashtable是线程安全，而HashMap则非线程安全

Hashtable的实现方法里面都添加了synchronized关键字来确保线程同步，因此相对而言HashMap性能会高一些，我们平时使用时若无特殊需求建议使用HashMap，在多线程环境下若使用HashMap需要使用Collections.synchronizedMap()方法来获取一个线程安全的集合（Collections.synchronizedMap()实现原理是Collections定义了一个SynchronizedMap的内部类，这个类实现了Map接口，在调用方法时使用synchronized来保证线程同步,当然了实际上操作的还是我们传入的HashMap实例，简单的说就是Collections.synchronizedMap()方法帮我们在操作HashMap时自动添加了synchronized来实现线程同步，类似的其它Collections.synchronizedXX方法也是类似原理）

HashMap可以使用null作为key，HashTable不可以使用null作为key值。

实现接口不同

默认容量不同，HashMap为16，HashTable为11，默认因子相同，为0。75