HashMap和HashTable底层原理以及常见面试题

1. HashMap和HashTable的区别

HashMap和HashTable都是Java中的重要容器类，它们的目的是为了存放和访问键值对。虽然它们的功能是相似的，但是它们在底层的实现和使用上有很大的不同。

1.1 HashMap

HashMap的底层是基于哈希表实现的，其键值对存储在Entry数组中，每一个键值对被封装为一个Entry对象，并通过hash算法来计算每一个键值对在数组中的位置。当出现hash冲突的时候，HashMap采用链表法来解决冲突。在JDK1.7中，如果同一个链表节点上的元素超过了8个，链表就会变成红黑树，以提高查找效率。而在JDK1.8中，链表和红黑树的存储方式变得更加灵活，可动态选择存储方式以提升性能。

HashMap的键和值都允许为null，但是键值对不能重复，即键相同，值不同的键值对仍然会被认为是一个。

1.2 HashTable

HashTable也是基于哈希表的实现，其基本的操作和HashMap是相似的，但是HashTable是线程安全的，它的所有方法都是同步的，因此在多线程环境下使用比较安全。Hashtable在进行插入或者查找操作时，会锁定整张哈希表，其他线程会被阻塞。在Java5之前，Hashtable是作为线程安全的哈希表出现的，但是由于同步锁的使用导致了性能较差，因此在Java5后，推荐使用ConcurrentHashMap。

HashTable不允许键或者值为null，而且Hashtable的方法全部使用同步修饰，会对性能带来影响。

因此，在单线程环境下，应该使用HashMap，而在多线程环境下，推荐使用ConcurrentHashMap。

2. HashMap和HashTable面试题

2.1 HashMap和HashTable的区别

这是HashMap和HashTable的经典面试题，但是应该注意的是，在回答该问题时，应该从以下几个方面考虑：

• 是否线程安全
• 是否允许null键值对
• 查找效率的不同
• 初始化的容量和负载因子的默认值的不同

2.2 HashTable的底层实现

HashTable是如何通过哈希表来解决哈希冲突的？

答案：HashTable 的底层是由一个Entry数组和基于拉链法的哈希表实现的。当哈希函数计算出的数组索引位置已经有值时，会以链表的方式解决哈希冲突，将键值对插入链表末尾。

2.3 HashMap的哈希冲突解决方法

HashMap如何解决哈希冲突的？

答案：当两个键的哈希值相同时，它们会被放在同一个位置的链表中。但是当某个链表上的元素数量超过了8个时，这个链表就会变成树形结构，以提高查询效率。如果元素数量小于等于6，则链表又会变回普通的链表结构。

3. 示例说明

下面来看一个示例

public class Demo {
    public static void main(String[] args){
        Map<String, Integer> map = new HashMap<>();
        map.put("hello", 1);
        map.put("world", 2);
        map.put("java", 3);
        System.out.println(map.get("hello"));
    }
}

运行上述代码，输出结果为：

1

可以看到，我们通过put方法向map中添加了三个键值对，然后通过get方法获取了hello对应的值。这说明了在HashMap中，可以通过key快速地获取到value。

下面再看一个HashTable的示例：

public class Demo {
    public static void main(String[] args){
        Hashtable<String, Integer> hashtable = new Hashtable<>();
        hashtable.put("hello", 1);
        hashtable.put("world", 2);
        hashtable.put("java", 3);
        System.out.println(hashtable.get("hello"));
    }
}

运行上述代码，输出结果为：

1

可以看到，虽然HashMap和HashTable的基本操作都是相似的，但是Hashtable的所有方法都使用同步修饰，因此在多线程环境下使用较安全。