面试总结二——数据结构

柔光的暖阳◎ 2022-05-18 08:06 174阅读 0赞

**1、HashMap高效存储原理**

a. 根据key计算得到key.hash = (h = k.hashCode()) ^ (h >>> 16)；

b. 根据key.hash计算得到桶数组的索引index = key.hash & (table.length - 1)，这样就找到该key的存放位置了：

① 如果该位置没有数据，用该数据新生成一个节点保存新数据，返回null；

② 如果该位置有数据是一个红黑树，那么执行相应的插入 / 更新操作；

③ 如果该位置有数据是一个链表，分三种情况一是该链表没有这个节点，另一个是该链表上有这个节点，注意这里判断的依据是key.hash是否一样： 如果该链表没有这个节点，那么采用尾插法新增节点保存新数据，返回null； 如果该链表已经有这个节点了，那么找到該节点并更新新数据，返回老数据；最后一种链表元素超过8个时，转为红黑树存储。

**2、HashMap与HashTable的区别**

1.  HashMap可以接受为null的键值(key)和值(value)，而Hashtable则不行。
2.  HashMap是非synchronized，而Hashtable是synchronized，这意味着Hashtable是线程安全的，多个线程可以共享一个Hashtable；而如果没有正确的同步的话，多个线程是不能共享HashMap的。Java 5提供了ConcurrentHashMap，它是HashTable的替代，比HashTable的扩展性更好。
3.  另一个区别是HashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的。所以当有其它线程改变了HashMap的结构（增加或者移除元素），将会抛出ConcurrentModificationException，但迭代器本身的remove()方法移除元素则不会抛出ConcurrentModificationException异常。但这并不是一个一定发生的行为，要看JVM。这条同样也是Enumeration和Iterator的区别。
4.  由于Hashtable是线程安全的也是synchronized，所以在单线程环境下它比HashMap要慢。如果你不需要同步，只需要单一线程，那么使用HashMap性能要好过Hashtable。
5.  HashMap不能保证随着时间的推移Map中的元素次序是不变的。

**3、List、Set、Map的区别**

1、List,Set都是继承自Collection接口，Map则不是  
     2、List特点：元素有放入顺序，元素可重复 ，Set特点：元素无放入顺序，元素不可重复，重复元素会覆盖掉，（注意：元素虽然无放入顺序，但是元素在set中的位置是有该元素的HashCode决定的，其位置其实是固定的，加入Set 的Object必须定义equals()方法 ，另外list支持for循环，也就是通过下标来遍历，也可以用迭代器，但是set只能用迭代，因为他无序，无法用下标来取得想要的值。）   
    3.Set和List对比：   
        Set：检索元素效率低下，删除和插入效率高，插入和删除不会引起元素位置改变。   
        List：和数组类似，List可以动态增长，查找元素效率高，插入删除元素效率低，因为会引起其他元素位置改变。  
    4.** **LinkedList、ArrayList、HashSet是非线程安全的，Vector是线程安全的;  
        HashMap是非线程安全的，HashTable是线程安全的;  
    5.Map适合键值对存储