Java集合详解( 二 ) _Java集合

文章插图

延伸一个面试题：HashSet是如何保证元素的唯一性？
当调用add()方法向集合中存入对象的时候，首先会使用 hash() 函数生成一个 int 类型的 hashCode 散列值，然后与已经存储的元素的 hashCode 值作比较，如果 hashCode 值不相等，则所存储的两个对象一定不相等，此时把这个新元素存储在它的 hashCode 位置上；如果 hashCode 相等，存储元素的对象还是不一定相等，此时会调用 equals() 方法判断两个对象的内容是否相等，如果 equals() 返回true，则是同一个对象，无需存储；如果 equals() 返回 false，那么就是不同的对象，就需要存储，不过由于 hashCode 相同，HashSet会以链式结构将两个对象保存在同一位置，这将导致性能下降，因此在编码时应避免出现这种情况。

List与Set选型List与Set都是存储对象的，那我们实际开发中应该如何选择呢？可以参考下图：

文章插图

MapMap用于保存具有映射关系的数据，Map里保存着两组数据：key和value，它们都可以使任何引用类型的数据，但key不能重复。所以通过指定的key就可以取出对应的value 。
Map接口有四个比较重要的实现类，分别是HashMap、LinkedHashMap、TreeMap和HashTable 。它们的区别如下：

HashMap的key值可以为null，但只能有一个key为null；它是线程不安全的，如果需要同步，可以用 Collections的synchronizedMap方法使HashMap具有同步的能力，或者使用ConcurrentHashMap 。
LinkedHashMap继承自HashMap，它主要是用链表实现来扩展HashMap类，HashMap中条目是没有顺序的，但是在LinkedHashMap中元素既可以按照它们插入的顺序排序，也可以按它们最后一次被访问的顺序排序。
TreeMap基于红黑树数据结构的实现，键值可以使用Comparable或Comparator接口来排序。TreeMap继承自AbstractMap，同时实现了接口NavigableMap，而接口NavigableMap则继承自SortedMap 。SortedMap是Map的子接口，使用它可以确保图中的条目是排好序的。
Hashtable和HashMap很类似，它也是一个散列表，存储的内容是键值对映射，不同之处在于，Hashtable是继承自Dictionary的，Hashtable中的函数都是同步的，这意味着它也是线程安全的，另外，Hashtable中key和value都不可以为null 。

文章插图

在实际使用中，如果更新时不需要保持元素的顺序，就使用HashMap，如果需要保持元素的插入顺序或者访问顺序，就使用LinkedHashMap，如果需要使图按照键值排序，就使用TreeMap 。
遍历Map的四种方式Map不同于List和Set，它存储的是key-value的键值对，不能像List和Set那样直接使用 for 循环遍历，可以通过下面四种方式遍历Map：

文章插图

必问面试题：HashMap的底层实现HashMap采用Entry数组来存储key-value对，每一个键值对组成了一个Entry实体，Entry类实际上是一个单向的链表结构，它具有Next指针，可以连接下一个Entry实体。只是在JDK1.8中，链表长度大于8的时候，链表会转成红黑树。
在调用 HashMap 的 put 方法添加元素时，会对key的hashCode()做hash运算，计算index; 如果没碰撞直接放到bucket里；如果碰撞了，以链表的形式存在buckets后；如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD)，就把链表转换成红黑树(JDK1.8中的改动)；如果节点已经存在就替换old value(保证key的唯一性) 如果bucket满了(超过load factor*current capacity)，就要resize 。
在调用 HashMap 的 get 方法获取元素时，会对key的hashCode()做hash运算，计算index; 如果在bucket里的第一个节点里直接命中，则直接返回；如果有冲突，则通过key.equals(k)去查找对应的Entry 。
上面只是简单的说了下 HashMap 在 put 和 get 时的主要过程，后期我会单独开一篇文章，根据 HashMap 的源码来说明它的具体原理。