程序员的基本功之Java集合的实现细节

1.Set集合与Map

仔细对比观察上面Set下和Map下的接口名，不难发现它们如此的相似，必有原因

如果只考察Map的Key会发现，它们不可以重复，没有顺序，也就是说把Map的所有的Key集中起来就是一个Set集合，所以map有了方法 Set<K> keySet();

对于Map而言，实际上他就相当于一个所有元素都是Key-Value的Set集合

问题：如何用Set实现一个Map？？

思路：定义一个SimpleEntry类，该类代表一个Key-Value对，当Set集合中的元素都是SimpleEntry时，该Set就可以当作Map来使得

HashMap和HashSet

对于HashSet而言，系统采用Hash算法决定集合元素的存储位置，这样可以保证快速存取集合元素

对于HashMap而言，系统将Value当成Key的附属，系统根据Hash算法来决定Key的存储位置，这样保证快速存取集合的Key，而Value总是跟紧随Key存储

虽然集合号称存储的Java对象，但实际上并不会真的把Java对象放入Set集合，而只是在Set集合中保留这些对象的引用

　　存储方式：

对于HashMap，程序执行map.put("语文"，80.0);时，系统调用 "语文" 的HashCode的方法，得出其HashCode值，HashMap根据其HashCode值来决定元素的存储位置

HashMap类的put(K key,V value)方法源代码如下(来自JDK 1.6 , JDK 1.8有所改进)

public V put(K key, V value) {
　　　　//如果key为null，调用putForNullKey方法进行处理
        if (key == null)
            return putForNullKey(value);
　　　　　　//根据Key的hashCode 值计算Hash值
        int hash = hash(key.hashCode());
　　　　　　//根据指定hash值查找对应table中的索引
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
　　　　　　　　//找到指定key与需要放入的key相等（hash值相同，并且通过equals方法比较返回true）
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
　　　　//如果i索引处的entry为null，表明此处没有entry
        modCount++;
　　　　//将key value 添加到索引i处
        addEntry(hash, key, value, i);
        return null;
    }

从上面的程序可以看出HashMap在存储Key-Value的时候没有考虑Value，仅仅根据Key来计算Entry的存储位置，Map.Entry是一个重要的接口，它代表了一个Key-Value对

从源代码中可以看出

　　当向HashMap中放入Key-Value对时，首先根据Key的HashCode值决定该Entry的存储位置

　　如果两个Entry的Key的HashCode值相等，那它们的存储位置相同

　　如果两个Entry的Key通过equals比较返回true，那么新添加的Entry的Value会覆盖原来的，但Key不会覆盖

　　如果两个Entry的Key通过equals比较返回false，那么新添加的Entry与集合中原来的Entry形成Entry链，新添加的Entry位于链的头部

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;//指向下一个entry 形成entry链
        final int hash;
        
        ........  
｝

void addEntry(int hash, K key, V value, int bucketIndex) {
　　//获取指定bucketIndex索引处的entry
    Entry<K,V> e = table[bucketIndex];
　　　　　　//将新创建的entry放入指定bucketIndex索引处，并让新的entry指向原来的entry  如果原来的bucketIndex处没有entry，则不会形成entry链
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
　　　　　　//如果map中的Key-Value对的数量超过了上限
        if (size++ >= threshold)
　　　　　　　　//把table对象的长度扩充到原来的2倍
            resize(2 * table.length);
    }

其中有两个参数：

　　size：该变量保存了hashmap中所包含的Key-Value对我数量

　　threshold：该变量表示hashmap所能容纳的Key-Value对的极限，它的值等于hashmap的容量乘以负载因子(loader factor)

　　table就是一个普通的数组，数组的长度就是hashmap的容量，table里面存储的就是hashmap的entry，table中存储元素的位置叫桶bucket

　　默认的HashMap()构造器会构造一个初始容量为16，负载因子为0.75的hashmap （0.75是时间与空间上的一种折衷）

public HashMap(int initialCapacity, float loadFactor) {
　　　　//初始容量不为为负数
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
   　　　//如果初始容量大于最大容量，让初始容量等于最大容量 　    
　　 　　if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
　　　　　　//负载因子必须大于0的数字
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);

        // Find a power of 2 >= initialCapacity
　　　　　　
　　　　//计算出大于initialCapacity的最小的2的n次方
        int capacity = 1;
        while (capacity < initialCapacity)
            capacity <<= 1;

        this.loadFactor = loadFactor;
　　　　　　//设置容量等于极限等于容量乘以负载因子
        threshold = (int)(capacity * loadFactor);
　　　　　　//初始化table数组
        table = new Entry[capacity];
        init();
    }

 public V get(Object key) {
        if (key == null)
            return getForNullKey();
        //根据key的hashcode值计算他的hash码
        int hash = hash(key.hashCode());
　　　　　　//直接取出table数组中指定索引处的值
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
　　　　　　　　
             e != null;
　　　　　　　　　　//搜索entry链的下一个entry
             e = e.next) {
            Object k;
　　　　　　　　//如果该entry的key与被搜索的key相同，就把value返回
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                return e.value;
        }
        return null;
    }

总结：HashMap底层将Key-Value当成一个整体进行处理，这个整体就是一个entry对象，底层采用一个Entry[]数组table来保存所有Key-Value对

需要存储一个Entry对象时会根据Hash算法来决定其存储位置，取出一个Entry时也会根据Hash算法来找他的位置，直接取出Entry

如果一开始就知道要在HashMap中存储多个Key-Value对时，可以在初始化指定一个较大的容量，省去resize的性能损耗

HashSet

HashSet底层是采用HashMap实现的，底层封装了一个HashMap，所有的HashSet集合中的元素实际是由HashMap中的Key来保存的，而Value是一个PRESENT,它是一个静态的Object对象

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    static final long serialVersionUID = -5024744406713321676L;
　　//使用hashmap的key保存hashset的值
    private transient HashMap<E,Object> map;
　　//定义一个虚拟的Object对象当作value的值
    private static final Object PRESENT = new Object();
　　//初始hashset底层会初始化一个hashmap
    public HashSet() {
    map = new HashMap<E,Object>();
    }
　　   
　　//以指定的参数创建一个hashset，底层是以指定的参数创建一个hashmap
    public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<E,Object>(initialCapacity, loadFactor);
    }

    public HashSet(int initialCapacity) {
    map = new HashMap<E,Object>(initialCapacity);
    }

    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
    }
　　//调用map的keyset返回所有的hashset值
    public Iterator<E> iterator() {
    return map.keySet().iterator();
    }

    public int size() {
    return map.size();
    }

    public boolean isEmpty() {
    return map.isEmpty();
    }

    public boolean contains(Object o) {
    return map.containsKey(o);
    }
　　//将指定元素放入hashset中，实际就是将元素的作为key放入hashmap中
    public boolean add(E e) {
    return map.put(e, PRESENT)==null;
    }

    public boolean remove(Object o) {
    return map.remove(o)==PRESENT;
    }

    public void clear() {
    map.clear();
    }
}

由于hashset底层是由hashmap实现的，那么根据hashmap的实现原理，当hashset中放入重复的元素时，不会覆盖原来的，只是value会覆盖

注意重写放入hashset和hashmap中的对象的hashcode方法和 equals方法很重要，并且要一至，当hashcode方法返回true时equals方法也要返回true才行

如何正确的重写hashCode方法和equals方法？

所有参与计算hashcode返回值的参数都应用于作为equals()比较的标准