HashMap底层实现原理及面试问题.pdf

HashMap底层实现原理及⾯试问题 ①HashMap的⼯作原理 HashMap基于hashing原理，我们通过put()和get()⽅法储存和获取对象。当我们将键值对传递给put()⽅法 时，它调⽤键对象的hashCode()⽅法来计算hashcode ，让后找到bucket位置来储存值对象。当获取对象 时，通过键对象的equals()⽅法找到正确的键值对，然后返回值对象。HashMap使⽤链表来解决碰撞问 题，当发⽣碰撞了，对象将会储存在链表的下⼀个节点中。 HashMap在每个链表节点中储存键值对对 象。 当两个不同的键对象的hashcode相同时会发⽣什么？ 它们会储存在同⼀个bucket位置的链表中。键对象 的equals()⽅法⽤来找到键值对。 因为HashMap的好处⾮常多，我曾经在电⼦商务的应⽤中使⽤HashMap作为缓存。因为⾦融领域⾮常多 的运⽤Java ，也出于性能的考虑，我们会经常⽤到HashMap和ConcurrentHashMap。 ②HashMap和Hashtable的区别 HashMap和Hashtable都实现了Map接⼝，但决定⽤哪⼀个之前先要弄清楚它们之间的分别。主要的区别 有：线程安全性，同步(synchronization) ，以及速度。 1. HashMap⼏乎可以等价于Hashtable ，除了HashMap是⾮synchronized的，并可以接受null(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中的元素次序是不变的。 要注意的⼀些重要术语： 1) sychronized意味着在⼀次仅有⼀个线程能够更改Hashtable。就是说任何线程要更新Hashtable时要⾸先 获得同步锁，其它线程要等到同步锁被释放之后才能再次获得同步锁更新Hashtable。 2) Fail-safe和iterator迭代器相关。如果某个集合对象创建了Iterator或者ListIterator ，然后其它的线程试图 “结构上”更改集合对象，将会抛出ConcurrentModificationException异常。但其它线程可以通过set()⽅法更 改集合对象是允许的，因为这并没有从“结构上”更改集合。但是假如已经从结构上进⾏了更改，再调⽤ set()⽅法，将会抛出IllegalArgumentException异常。 3) 结构上的更改指的是删除或者插⼊⼀个元素，这样会影响到map的结构。 我们能否让HashMap同步？ HashMap可以通过下⾯的语句进⾏同步： Map m = Collections.synchronizeMap(hashMap); 结论 Hashtable和HashMap有⼏个主要的不同：线程安全以及速度。仅在你需要完全的线程安全的时候使⽤ Hashtable ，⽽如果你使⽤Java 5或以上的话，请使⽤ConcurrentHashMap吧。 ashMap和HashSet的区别是Java⾯试中最常被问到的问题。如果没有涉及到Collection框架以及多线程的⾯ 试，可以说是不完整。⽽Collection框架的问题不涉及到HashSet和HashMap ，也可以说是不完整。