集合面试一

HashMap，LinkedMap，TreeMap的区别

PriorityQueue 保证最高或者最低优先级的的元素总是在队列头部，但是 LinkedHashMap 维持的顺序是元素插入的顺序。

LinkedHashMap是HashMap的子类。

HashMap的put方法会引起死循环，让CPU的利用率达到100%

TreeMap是已经排序好了，而HashMap是没有排序的，

如果要按值排序可以如下：

public class MapUtil
{
    public static <K, V extends Comparable<? super V>> Map<K, V> 
        sortByValue( Map<K, V> map )
    {
        List<Map.Entry<K, V>> list =
            new LinkedList<Map.Entry<K, V>>( map.entrySet() );
        Collections.sort( list, new Comparator<Map.Entry<K, V>>()
        {
            public int compare( Map.Entry<K, V> o1, Map.Entry<K, V> o2 )
            {
                return (o1.getValue()).compareTo( o2.getValue() );
            }
        } );

        Map<K, V> result = new LinkedHashMap<K, V>();
        for (Map.Entry<K, V> entry : list)
        {
            result.put( entry.getKey(), entry.getValue() );
        }
        return result;
    }
}

1.HashMap的内部结构是一个数组，线性顺序存储，二次结构使用线性的单链表。使用key的hashCode做二次hash之后，再截取小于数组长度的值为索引值。key可以为null，存在索引为0的位置上。由于使用了数组，所以有一个负载因子loadFactor的概念（临界阈值threshold）和resize。resize比较耗时，冲突时链式遍历查找也比较耗时，所以选定一个合适的初始容易比较重要。存取性能都较高。迭代遍历时一维使用数组，二维使用链表。【这种数据结构的设计模式】

HashMap是一个最常用的Map,它根据键的HashCode 值存储数据,根据键可以直接获取它的值，具有很快的访问速度。HashMap最多只允许一条记录的键为Null;允许多条记录的值为 Null;

2.LinkedHashMap是HashMap的子类。内部结构是一个数组，线性顺序存储，二次结构使用线性的单链表，但同时内部维护了一个双向循环链表,可以保持顺序。access-order=false默认为使用新增存储顺序，access-order=true则指定使用读取和访问顺序。removeEldestEntry=false（当指定为true时，就是实现LRU算法的缓存容器，当然要指定淘汰时的使用频率和容量上限，其实是一个最近最少使用-->最近使用access-order=true/最新存储access-order=false）。存取性能较HashMap差－些，但相差不大。header.after为尾方向，header.before为首方向。迭代遍历时entrySet().iterator()跟HashMap一样(有点困惑，为什么不按线性顺序进行迭代，只能重写entrySet(),keySet()和values()方法)。适用于有缓存设计需求的情况（需继承）。

3.TreeMap的内部结构是一棵红黑树（又叫排序数，是二叉树的一种），使用链式存储，可以指定比较器Comparator，key需实现Comparable接口。key不能为null。存结点性能稍差，因为需要调整树结构；取结点用的是链表遍历，但是属于有序比较，性能中等。迭代遍历时用的树的中序遍历，是一个有序序列。适用于有排序需求的情况。

如果需要数据进行按照键值、或者是value值，则使用treeMap

HashSet和HashMap的区别

HashMap	HashSet

使用put()方法将元素放入map中	使用add()方法将元素放入set中
HashMap中使用键对象来计算hashcode值	HashSet使用成员对象来计算hashcode值，对于两个对象来说hashcode可能相同，所以equals()方法用来判断对象的相等性，如果两个对象不同的话，那么返回false
HashMap比较快，因为是使用唯一的键来获取对象	HashSet较HashMap来说比较慢

HashSet有以下特点：

A. 无序（不能保证元素的排列顺序，顺序有可能发生变化）B. 不同步C. 允许空值（集合元素可以是null,可以放入多个null，但会自动覆盖）

当向HashSet结合中存入一个元素时，HashSet会调用该对象的hashCode()方法来得到该对象的hashCode值，然后根据 hashCode值来决定该对象在HashSet中存储位置。简单的说，HashSet集合判断两个元素相等的标准是两个对象通过equals方法比较相等，并且两个对象的hashCode()方法返回值相等注意，如果要把一个对象放入HashSet中，重写该对象对应类的equals方法，也应该重写其hashCode()方法。其规则是如果两个对象通过equals方法比较返回true时，其hashCode也应该相同。另外，对象中用作equals比较标准的属性，都应该用来计算 hashCode的值。

TreeSet有以下特点：

A. 有序

1. TreeSet是由一个树形的结构来实现的（数据结构是二叉树），它里面元素是有序的

2.TreeSet是SortedSet接口的唯一实现类，TreeSet可以确保集合元素处于排序状态，支持两种排序方式，自然排序和定制排序。其中自然排序为默认的排序方式；定制排序，TreeSet中的对象元素需要实Comparable接口

TreeSet类中跟HashSet类一样也没有get()方法来获取列表中的元素，所以也只能通过迭代器方法来获取

二叉树：

B. 不允许空值

1. HashSet是通过HashMap实现的,TreeSet是通过TreeMap实现的,只不过Set用的只是Map的key【？？？】

3. TreeSet类中跟HashSet类一样也没有get()方法来获取列表中的元素，所以也只能通过迭代器方法来获取

4. HashSet是基于hash算法实现的，性能优于TreeSet，通常使用HashSet。在我们需要对其中元素排序的时候才使用TreeSet。

复杂点：

从weak reference特性来看，肯定是用于监测对象状态。至于我使用的时候嘛。。很少会直接用到它，大多数时候需要针对线程作为键进行映射，直接使用ThreadLocal就好了。
我直接使用好像只有两次，都是对Class对象作为键进行映射。由于类加载器的缘故，可能发生Class的回收，若使用强引用，内存开销可能会太大。
总之，对于那些很可能被回收，而且被放置在static字段里的对象，就要用WeakHashMap
也可以做缓存，不过缓存还是用SoftReference比较好，soft reference在内存将满时会丢弃引用。或者重载“删除第一个entry”方法(具体是什么名称忘记了。。)的LinkedHashMap，可以很轻松的实现LRU。