葡京网投哪个正规 > 新葡亰-编程 > 葡京网投哪个正规源码解析,java集合框架总结

原标题:葡京网投哪个正规源码解析,java集合框架总结

浏览次数:102 时间:2020-01-11

源码剖析

首先从构造函数开始讲,HashMap遵循集合框架的约束,提供了一个参数为空的构造函数与有一个参数且参数类型为Map的构造函数。除此之外,还提供了两个构造函数,用于设置HashMap的容量(capacity)与平衡因子(loadFactor)。

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    threshold = initialCapacity;
    init();
}
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
    this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}

从代码上可以看到,容量与平衡因子都有个默认值,并且容量有个最大值

/**
 * The default initial capacity - MUST be a power of two.
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
 * The maximum capacity, used if a higher value is implicitly specified
 * by either of the constructors with arguments.
 * MUST be a power of two <= 1<<30.
 */
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
 * The load factor used when none specified in constructor.
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

可以看到,默认的平衡因子为0.75,这是权衡了时间复杂度与空间复杂度之后的最好取值(JDK说是最好的),过高的因子会降低存储空间但是查找(lookup,包括HashMap中的put与get方法)的时间就会增加。

这里比较奇怪的是问题:容量必须为2的指数倍(默认为16),这是为什么呢?解答这个问题,需要了解HashMap中哈希函数的设计原理。

通过keyset遍历

葡京正网网投 1葡京正网网投 2

public class HashMapTest {

    public static void main(String[] args) {
        HashMap<String,String> map = new HashMap<String,String>();
        map.put("001", "zhangsan1");
        map.put("002", "zhangsan2");
        map.put("003", "zhangsan3");
        map.put("004", "zhangsan4");

        Set<String> keySet = map.keySet();
        Iterator<String> it = keySet.iterator();

        while(it.hasNext()) {
            String obj = (String)it.next();
            System.out.println(obj + "-" + map.get(obj));
        }
    }
}

运行结果:
004-zhangsan4
001-zhangsan1
002-zhangsan2
003-zhangsan3

View Code

2. <a name='HashMap-1'></a>HashMap实现机制

HashMap底层是基于数组和链表来实现的,主要通过计算散列码来决定存储的位置。HashMap中主要是通过key的hashCode来计算hash值的,只要hashCode相同,计算出来的hash值就一样。如果存储的对象对多了,就有可能不同的对象所算出来的hash值是相同的,这就出现了所谓的hash冲突。学过数据结构的同学都知道,解决hash冲突的方法有很多,HashMap底层是通过链表来解决hash冲突的。

葡京正网网投 3

hashmap链表图.jpg

图中,紫色部分即代表哈希表,也称为哈希数组,数组的每个元素都是一个单链表的头节点,链表是用来解决冲突的,如果不同的key映射到了数组的同一位置处,就将其放入单链表中。
下面来看看单链表节点的Entry类实现代码:

  /** Entry是单向链表。
  * 它是 “HashMap链式存储法”对应的链表。
  * 它实现了Map.Entry 接口,即实现getKey(), getValue(), setValue(V value), equals(Object o), hashCode()这些函数
  */
  static class Entry<K,V> implements Map.Entry<K,V> {
      final K key;
      V value;
      Entry<K,V> next;
      int hash;

      /**
       * Creates new entry.
      */
      Entry(int h, K k, V v, Entry<K,V> n) {
          value = v;
          next = n;
          key = k;
          hash = h;
      }

      public final K getKey() {
          return key;
      }

      public final V getValue() {
          return value;
      }

      public final V setValue(V newValue) {
          V oldValue = value;
          value = newValue;
          return oldValue;
      }

      // 若两个Entry的“key”和“value”都相等,则返回true。
      public final boolean equals(Object o) {
          if (!(o instanceof Map.Entry))
              return false;
          Map.Entry e = (Map.Entry)o;
          Object k1 = getKey();
          Object k2 = e.getKey();
          if (k1 == k2 || (k1 != null && k1.equals(k2))) {
              Object v1 = getValue();
              Object v2 = e.getValue();
              if (v1 == v2 || (v1 != null && v1.equals(v2)))
                  return true;
          }
          return false;
      }

      // key的hashCode 异或 value的hashCode
      public final int hashCode() {
          return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
      }

      public final String toString() {
          return getKey() + "=" + getValue();
      }

      /**
      * This method is invoked whenever the value in an entry is
      * overwritten by an invocation of put(k,v) for a key k that's already
      * in the HashMap.
      */
      void recordAccess(HashMap<K,V> m) {
      }

      /**
      * This method is invoked whenever the entry is
      * removed from the table.
      */
      void recordRemoval(HashMap<K,V> m) {
      }
  }

HashMap其实就是一个Entry数组,Entry对象中包含了键和值,其中next也是一个Entry对象,它就是用来处理hash冲突的,形成一个链表。

public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, java.io.Serializable

继上一篇文章Java集合框架综述后,今天正式开始分析具体集合类的代码,首先以既熟悉又陌生的HashMap开始。

Collections

Collections是一个工具类,提供了操作集合的常用方法:

 

<!--排序, 对list中元素按升序进行排序,list中的所有元素都必须实现 Comparable 接口-->
void sort(List<T> list)

<!--混排,打乱list中元素的顺序-->
void shuffle(List<?> list)

<!--反转,反转list中元素的顺序-->
void reverse(List<?> list)

<!--使用指定元素替换指定列表中的所有元素-->
void fill(List<? super T> list, T obj)

<!-- 将源list中的元素拷贝到目标list-->
void copy(List<? super T> dest, List<? extends T> src)

<!-- 返回集合中最小的元素-->
T min(Collection<? extends T> coll)

<!-- 返回集合中最大的元素-->
T max(Collection<? extends T> coll)

6.2. <a name='-7'></a>扩容容

重新调整HashMap的大小,newCapacity是调整后的单位.

  void resize(int newCapacity) {
      Entry[] oldTable = table;
      int oldCapacity = oldTable.length;
      if (oldCapacity == MAXIMUM_CAPACITY) {
          threshold = Integer.MAX_VALUE;
          return;
      }

      Entry[] newTable = new Entry[newCapacity];
      transfer(newTable, initHashSeedAsNeeded(newCapacity));
      table = newTable;
      threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
  }

新建了一个HashMap的底层数组,上面代码中第10行为调用transfer方法,将HashMap的全部元素添加到新的HashMap中,并重新计算元素在新的数组中的索引位置

当HashMap中的元素越来越多的时候,hash冲突的几率也就越来越高,因为数组的长度是固定的。所以为了提高查询的效率,就要对HashMap的数组进行扩容,数组扩容这个操作也会出现在ArrayList中,这是一个常用的操作,而在HashMap数组扩容之后,最消耗性能的点就出现了:原数组中的数据必须重新计算其在新数组中的位置,并放进去,这就是resize。
如果我们已经预知HashMap中元素的个数,那么预设元素的个数能够有效的提高HashMap的性能。

static final float DEFAULT_LOAD_FACTOR = 0.75f;

put操作(含update操作)

因为put操作有可能需要对HashMap进行resize,所以实现略复杂些

private void inflateTable(int toSize) {
    //辅助函数,用于填充HashMap到指定的capacity
    // Find a power of 2 >= toSize
    int capacity = roundUpToPowerOf2(toSize);
    //threshold为resize的阈值,超过后HashMap会进行resize,内容的entry会进行rehash
    threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    table = new Entry[capacity];
    initHashSeedAsNeeded(capacity);
}
/**
 * Associates the specified value with the specified key in this map.
 * If the map previously contained a mapping for the key, the old
 * value is replaced.
 */
public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    //这里的循环是关键
    //当新增的key所对应的索引i,对应table[i]中已经有值时,进入循环体
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        //判断是否存在本次插入的key,如果存在用本次的value替换之前oldValue,相当于update操作
        //并返回之前的oldValue
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    //如果本次新增key之前不存在于HashMap中,modCount加1,说明结构改变了
    modCount++;
    addEntry(hash, key, value, i);
    return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
    //如果增加一个元素会后,HashMap的大小超过阈值,需要resize
    if ((size >= threshold) && (null != table[bucketIndex])) {
        //增加的幅度是之前的1倍
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }
    createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
    //首先得到该索引处的冲突链Entries,有可能为null,不为null
    Entry<K,V> e = table[bucketIndex];
    //然后把新的Entry添加到冲突链的开头,也就是说,后插入的反而在前面(第一次还真没看明白)
    //需要注意的是table[bucketIndex]本身并不存储节点信息,
    //它就相当于是单向链表的头指针,数据都存放在冲突链中。
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}
//下面看看HashMap是如何进行resize,庐山真面目就要揭晓了
void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    //如果已经达到最大容量,那么就直接返回
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }
    Entry[] newTable = new Entry[newCapacity];
    //initHashSeedAsNeeded(newCapacity)的返回值决定了是否需要重新计算Entry的hash值
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    table = newTable;
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
/**
 * Transfers all entries from current table to newTable.
 */
void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    //遍历当前的table,将里面的元素添加到新的newTable中
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            //最后这两句用了与put放过相同的技巧
            //将后插入的反而在前面
            newTable[i] = e;
            e = next;
        }
    }
}
/**
 * Initialize the hashing mask value. We defer initialization until we
 * really need it.
 */
final boolean initHashSeedAsNeeded(int capacity) {
    boolean currentAltHashing = hashSeed != 0;
    boolean useAltHashing = sun.misc.VM.isBooted() &&
            (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
    //这里说明了,在hashSeed不为0或满足useAltHash时,会重算Entry的hash值
    //至于useAltHashing的作用可以参考下面的链接
    // http://stackoverflow.com/questions/29918624/what-is-the-use-of-holder-class-in-hashmap
    boolean switching = currentAltHashing ^ useAltHashing;
    if (switching) {
        hashSeed = useAltHashing
            ? sun.misc.Hashing.randomHashSeed(this)
            : 0;
    }
    return switching;
}

集合工具类

6. <a name='putget-5'></a>put和get方法

  1. 非树形阈值,JDK1.8新增

哈希函数的设计原理

/**
  * Retrieve object hash code and applies a supplemental hash function to the
  * result hash, which defends against poor quality hash functions.  This is
  * critical because HashMap uses power-of-two length hash tables, that
  * otherwise encounter collisions for hashCodes that do not differ
  * in lower bits. Note: Null keys always map to hash 0, thus index 0.
  */
 final int hash(Object k) {
     int h = hashSeed;
     if (0 != h && k instanceof String) {
         return sun.misc.Hashing.stringHash32((String) k);
     }
     h ^= k.hashCode();
     // This function ensures that hashCodes that differ only by
     // constant multiples at each bit position have a bounded
     // number of collisions (approximately 8 at default load factor).
     h ^= (h >>> 20) ^ (h >>> 12);
     return h ^ (h >>> 7) ^ (h >>> 4);
 }
 /**
  * Returns index for hash code h.
  */
 static int indexFor(int h, int length) {
     // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
     return h & (length-1);
 }

看到这么多位操作,是不是觉得晕头转向了呢,还是搞清楚原理就行了,毕竟位操作速度是很快的,不能因为不好理解就不用了。

网上说这个问题的也比较多,我这里根据自己的理解,尽量做到通俗易懂。

在哈希表容量(也就是buckets或slots大小)为length的情况下,为了使每个key都能在冲突最小的情况下映射到[0,length)(注意是左闭右开区间)的索引(index)内,一般有两种做法:

  1. 让length为素数,然后用hashCode(key) mod length的方法得到索引
  2. 让length为2的指数倍,然后用hashCode(key) & (length-1)的方法得到索引

HashTable用的是方法1,HashMap用的是方法2。

因为本篇主题讲的是HashMap,所以关于方法1为什么要用素数,我这里不想过多介绍,大家可以看这里。

重点说说方法2的情况,方法2其实也比较好理解:

因为length为2的指数倍,所以length-1所对应的二进制位都为1,然后在与hashCode(key)做与运算,即可得到[0,length)内的索引

但是这里有个问题,如果hashCode(key)的大于length的值,而且hashCode(key)的二进制位的低位变化不大,那么冲突就会很多,举个例子:

Java中对象的哈希值都32位整数,而HashMap默认大小为16,那么有两个对象那么的哈希值分别为:0xABAB00000xBABA0000,它们的后几位都是一样,那么与16异或后得到结果应该也是一样的,也就是产生了冲突。

造成冲突的原因关键在于16限制了只能用低位来计算,高位直接舍弃了,所以我们需要额外的哈希函数而不只是简单的对象的hashCode方法了。

具体来说,就是HashMap中hash函数干的事了

首先有个随机的hashSeed,来降低冲突发生的几率

然后如果是字符串,用了sun.misc.Hashing.stringHash32((String) k);来获取索引值

最后,通过一系列无符号右移操作,来把高位与低位进行异或操作,来降低冲突发生的几率

右移的偏移量20,12,7,4是怎么来的呢?因为Java中对象的哈希值都是32位的,所以这几个数应该就是把高位与低位做异或运算,至于这几个数是如何选取的,就不清楚了,网上搜了半天也没统一且让人信服的说法,大家可以参考下面几个链接:

Collections举例

葡京正网网投 4葡京正网网投 5

public class CollectionsTest {

    public static void main(String[] args) {
        ArrayList al = new ArrayList();
        al.add("zhangsan");
        al.add("lisi");
        al.add("wangwu");

        System.out.println("集合未排序前");
        System.out.println(al);

        System.out.println("使用Collections.sort()方法自然排序");
        Collections.sort(al);
        System.out.println(al);

        System.out.println("使用Comparator按长度自定义排序");
        Collections.sort(al,new StringLengthComparator());
        System.out.println(al);

        System.out.println("al中最长的元素");
        System.out.println(Collections.max(al,new StringLengthComparator()));

        System.out.println("已排序的前提下,wangwu元素下标索引");
        System.out.println(Collections.binarySearch(al, "wangwu"));

        System.out.println("逆序");
        Collections.reverse(al);
        System.out.println(al);

    }
}

class StringLengthComparator implements Comparator<String> {

    @Override
    public int compare(String o1, String o2) {
        if(o1.length() > o2.length()) 
            return 1;
        if(o1.length() < o2.length())
            return -1;
        return 0;
    }
}

运行结果:
集合未排序前
[zhangsan, lisi, wangwu]
使用Collections.sort()方法自然排序
[lisi, wangwu, zhangsan]
使用Comparator按长度自定义排序
[lisi, wangwu, zhangsan]
al中最长的元素
zhangsan
已排序的前提下,wangwu元素下标索引
1
逆序
[zhangsan, wangwu, lisi]

View Code

7. <a name='HashMap-9'></a>HashMap的性能参数

HashMap 包含如下几个构造器:

HashMap():构建一个初始容量为 16,负载因子为 0.75 的 HashMap。

HashMap(int initialCapacity):构建一个初始容量为 initialCapacity,负载因子为 0.75 的 HashMap。

HashMap(int initialCapacity, float loadFactor):以指定初始容量、指定的负载因子创建一个 HashMap。

HashMap的基础构造器HashMap(int initialCapacity, float loadFactor)带有两个参数,它们是初始容量initialCapacity和加载因子loadFactor。

initialCapacity:HashMap的最大容量,即为底层数组的长度。

loadFactor:负载因子loadFactor定义为:散列表的实际元素数目(n)/ 散列表的容量(m)。

负载因子衡量的是一个散列表的空间的使用程度,负载因子越大表示散列表的装填程度越高,反之愈小。对于使用链表法的散列表来说,查找一个元素的平均时间是O(1+a),因此如果负载因子越大,对空间的利用更充分,然而后果是查找效率的降低;如果负载因子太小,那么散列表的数据将过于稀疏,对空间造成严重浪费。

HashMap的实现中,通过threshold字段来判断HashMap的最大容量:

threshold = (int)(capacity * loadFactor);

结合负载因子的定义公式可知,threshold就是在此loadFactor和capacity对应下允许的最大元素数目,超过这个数目就重新resize,以降低实际的负载因子。默认的的负载因子0.75是对空间和时间效率的一个平衡选择。当容量超出此最大容量时, resize后的HashMap容量是容量的两倍:

HashMap的默认加载因子是0.75,这是在时间和空间两方面的考虑。加载因子太大的话,产生冲突的可能性就会很大,查找的效率就会降低。太小的话,需要频繁rehash,导致性能低。

Cloneable接口

<code>It's evil, don't use it. </code>

Cloneable这个接口设计的非常不好,最致命的一点是它里面竟然没有clone方法,也就是说我们自己写的类完全可以实现这个接口的同时不重写clone方法。

关于Cloneable的不足,大家可以去看看《Effective Java》一书的作者给出的理由,在所给链接的文章里,Josh Bloch也会讲如何实现深拷贝比较好,我这里就不在赘述了。

HashMap

HashMap是Map接口的一个实现类,它存储的内容是键值对(key-value)。HashMap的底层是哈希表数据结构,允许存储null的键和值,同时HashMap是线程不安全的。HashMap与HashTable的区别是:HashTable不可以存储null的键和值,HashTable是线程安全的(synchronized实现)。

 

哈希表的定义:给定表M,存在函数f(key),对任意给定的关键字值key,代入函数后若能得到包含该关键字的记录在表中的地址,则称表M为哈希(Hash)表,函数f(key)为哈希(Hash) 函数。通过把关键字值key映射到哈希表中的一个位置来访问记录,以加快查找的速度。

 

HashMap定义如下:

public class HashMap<K,V>
    extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable
{}

l HashMap继承AbstractMap,AbstractMap抽象了Map集合的一些基本操作。

l HashMap实现了Cloneable,Serializable接口以便支持克隆和序列化。

 

HashMap源码分析总结(源码略,建议先整体认识再打开源码对着看):

 

l HashMap的几个重要成员:table, DEFAULT_INITIAL_CAPACITY ,MAXIMUM_CAPACITY ,

size, threshold, loadFactor, modCount。

(1)table是一个Entry[]数组类型,Map.Entry是一个Map接口里的一个内部接口。而Entry实际上就是一个单向链表,也称为HashMap的“数组+链式存储法”,链式存储是为了解决哈希冲突而存在。HashMap的键值对就是存储在Entry对象中(一个Entry对象包含一个key、一个value、key对应的hash和指向下一个Entry的对象)。

(2)DEFAULT_INITIAL_CAPACITY是默认的初始容量是16。

(3)MAXIMUM_CAPACITY, 最大容量(初始化容量大于这个值时将被这个值替换)。

(4)size是HashMap的大小,保存的键值对的数量。

(5)threshold是HashMap的阈值,用于判断是否需要调整HashMap的容量。threshold的值="容量*加载因子",当HashMap中存储数据的数量达到threshold时,就需要将HashMap进行rehash 操作(即重建内部数据结构)是容量*2。

(6)loadFactor就是加载因子。

(7)modCount是记录HashMap被修改的次数。

 

l table分配空间。不同版本略有差异。在1.6的源码中,为table分配空间是在HashMap的构造函数中,而1.7的中,则在put的时候先判断table是否为空,为空则分配空间。

l get(Object key)。先计算key的hash,根据hash计算索引,根据索引在table数组中查找出对应的Entry,返回Entry中的value。

l put(K key, V value)。若key为null,则创建一个key为null的Entry对象并存储到table[0]中。否则计算其hash以及索引i,创建一个键值对和哈希值分别为key、value、hash的Entry对象并存储到table[i]中(若table[i]处为空即没有Entry链表则直接存入,否则将Entry对象添加到table[i]处的Entry链表的表头中)。需要注意的是,如果该hash已经存在Entry链表中,则用新的value取代旧的value并返回旧的value。

l  putAll(Map<? extends K, ? extends V> m)。当当前实际容量小于需要的容量,则将容量*2。调用put()方法逐个添加到HashMap中。

l remove(Object key)。计算key的hash以及索引i,根据索引在table数组中查找出对应的Entry,从Entry链表删除对应的Entry节点,期间会比较hash和key(equals判断)来判断是否是要删除的节点。

l clear()。把每一个table[i]设置为null。

l Entry类中重写了equals()方法和hashCode()来判断两个Entry是否相等。

l containsKey(Object key)。比较hash和key(equals判断)来判断是否是包含该key。

 

葡京正网网投 6

 

 

HashMap内存结构示意图

 

6.1. <a name='-6'></a>存储数据

  public V put(K key, V value) {
      if (table == EMPTY_TABLE) {
          inflateTable(threshold);
      }
      if (key == null)
          return putForNullKey(value);
      int hash = hash(key);
      int i = indexFor(hash, table.length);
      // 循环遍历Entry数组,若“该key”对应的键值对已经存在,则用新的value取代旧的value。然后退出!
      for (Entry<K,V> e = table[i]; e != null; e = e.next) {
          Object k;
          if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
              V oldValue = e.value;
              e.value = value;
              e.recordAccess(this);
              return oldValue;
          }
      }

      modCount++;
      // 将key-value添加到table[i]处将key-value添加到table[i]处
      addEntry(hash, key, value, i);
      return null;
  }

上面的程序中用到了一个重要的内部接口:Map.Entry,每个Map.Entry就是一个key-value对。从上面的程序中可以看出:当系统决定存储HashMap中的key-value时,完全没有考虑Entry中的value,仅仅只是根据key来计算并存储没有Entry的存储位置。这也说明了前面的结论:我们完全可以把 Map 集合中的 value 当成 key 的附属,当系统决定了 key 的存储位置之后,value 随之保存在那里即可。

我们慢慢的来分析这个函数,第2和3行的作用就是处理key值为null的情况,我们看看putForNullKey(value)方法:

  private V putForNullKey(V value) {
      for (Entry<K,V> e = table[0]; e != null; e = e.next) {
          if (e.key == null) {
              V oldValue = e.value;
              e.value = value;
              e.recordAccess(this);
              return oldValue;
          }
      }
      modCount++;
      addEntry(0, null, value, 0);
      return null;
  }

如果key为null的话,hash值为0,对象存储在数组中索引为0的位置。即table[0]。

通过key得到hash码之后,就会通过hash码去计算出应该存储在数组中的索引,计算索引的函数如下:

  static int indexFor(int h, int length) {
      // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
      return h & (length-1);
  }

这个我们要重点说下,我们一般对哈希表的散列很自然地会想到用hash值对length取模(即除法散列法),Hashtable中也是这样实现的,这种方法基本能保证元素在哈希表中散列的比较均匀,但取模会用到除法运算,效率很低,HashMap中则通过h&(length-1)的方法来代替取模,同样实现了均匀的散列,但效率要高很多,这也是HashMap对Hashtable的一个改进。

  void addEntry(int hash, K key, V value, int bucketIndex) {
      if ((size >= threshold) && (null != table[bucketIndex])) {
          resize(2 * table.length);
          hash = (null != key) ? hash(key) : 0;
          bucketIndex = indexFor(hash, table.length);
      }

      createEntry(hash, key, value, bucketIndex);
  }

  void createEntry(int hash, K key, V value, int bucketIndex) {
      Entry<K,V> e = table[bucketIndex];
      table[bucketIndex] = new Entry<>(hash, key, value, e);
      size++;
  }

参数bucketIndex就是indexFor函数计算出来的索引值,通过判断size大于临界值和当前定位不为空时就扩容,扩容为原来的两倍。该位置原先的值设置为新entry的next,也就是新entry链表的下一个节点。

TreeMap是基于红黑树实现的有序键值对集合,该映射根据键的自然顺序或传入的比较器进行排序,具体取决于使用的构造函数。TreeMap的基本操作containsKey、get、put和remove的时间复杂度为log。TreeMap继承了AbstractMap抽象类,并且实现了NavigableMap、Cloneable、Serializable接口。

HashMap的一些特点

  • 线程非安全,并且允许key与value都为null值,HashTable与之相反,为线程安全,key与value都不允许null值。
  • 不保证其内部元素的顺序,而且随着时间的推移,同一元素的位置也可能改变(resize的情况)
  • put、get操作的时间复杂度为O(1)。
  • 遍历其集合视角的时间复杂度与其容量(capacity,槽的个数)和现有元素的大小(entry的个数)成正比,所以如果遍历的性能要求很高,不要把capactiy设置的过高或把平衡因子(load factor,当entry数大于capacity*loadFactor时,会进行resize,reside会导致key进行rehash)设置的过低。
  • 由于HashMap是线程非安全的,这也就是意味着如果多个线程同时对一hashmap的集合试图做迭代时有结构的上改变(添加、删除entry,只改变entry的value的值不算结构改变),那么会报ConcurrentModificationException,专业术语叫fail-fast,尽早报错对于多线程程序来说是很有必要的。
  • Map m = Collections.synchronizedMap(new HashMap(...)); 通过这种方式可以得到一个线程安全的map。

Arrays举例

葡京正网网投 7葡京正网网投 8

public class ArraysTest {
    public static void main(String[] args) {
        String[] array = new String[]{"abc","def","hig"};
        System.out.println(Arrays.toString(array));

        List<String> list = Arrays.asList(array);
        System.out.println(list.contains("def"));
        //list.add("lmn");//UnsupportedOperationException

        int[] array2 = new int[]{1,2,3};
        List<int[]> list2 = Arrays.asList(array2);
        System.out.println(list2);

        Integer[] array3 = new Integer[]{1,2,3};
        List<Integer> list3 = Arrays.asList(array3);
        System.out.println(list3);
    }
}

运行结果:
[abc, def, hig]
true
[[I@36db4bcf]
[1, 2, 3]

View Code

需要注意的是,将数组变成集合后,不能使用集合的增加或者删除方法,因此数组的长度是固定的,使用这些方法将会报UnsupportedOperationException异常。从上面的例子也可以看出,如果数组中的元素都是对象,那么转换成集合时,数组中的元素就直接转换成集合中的元素;如果数组中的元素是基本类型,那么整个数组将作为集合的元素存在。

5. <a name='-4'></a>构造函数

  public HashMap(int initialCapacity, float loadFactor) {
      if (initialCapacity < 0)
          throw new IllegalArgumentException("Illegal initial capacity: " +
                                             initialCapacity);
      if (initialCapacity > MAXIMUM_CAPACITY)
          initialCapacity = MAXIMUM_CAPACITY;
      if (loadFactor <= 0 || Float.isNaN(loadFactor))
          throw new IllegalArgumentException("Illegal load factor: " +
                                             loadFactor);

      this.loadFactor = loadFactor;
      threshold = initialCapacity;
      init();
  }

  public HashMap(int initialCapacity) {
      this(initialCapacity, DEFAULT_LOAD_FACTOR);
  }

  public HashMap() {
      this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
  }

  // 构造一个与给定的 Map 具有相同映射关系的新哈希表。
  public HashMap(Map<? extends K, ? extends V> m) {
      this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                    DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
      inflateTable(threshold);

      putAllForCreate(m);
  }

这么多的构造函数,主要还是调用第一个构造函数。我们也没有看到Entry[]数据的创建,所以当前的table还只是一个默认的空数据(EMPTY_TABLE),并没有初始化数组的容量。如果不设置容量参数和加载因子的话,默认初始容量为16,默认加载因子为0.75。
最后一个对于集成map的集合类的初始化就进行了Entry数组的设置。inflateTable方法初始化一个容量膨胀到2的整数次幂大于等于(threshold-1)<<1的值的table。

  private void inflateTable(int toSize) {
      // Find a power of 2 >= toSize
      int capacity = roundUpToPowerOf2(toSize);

      threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
      table = new Entry[capacity];
      initHashSeedAsNeeded(capacity);
  }

  private static int roundUpToPowerOf2(int number) {
      // assert number >= 0 : "number must be non-negative";
      return number >= MAXIMUM_CAPACITY
              ? MAXIMUM_CAPACITY
              : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
  }

  // 返回二进制中最高位为1的值  也可以说小于等于i的最大2的次幂
  public static int highestOneBit(int i) {
      // HD, Figure 3-1
      i |= (i >>  1);
      i |= (i >>  2);
      i |= (i >>  4);
      i |= (i >>  8);
      i |= (i >> 16);
      return i - (i >>> 1);
  }

  final boolean initHashSeedAsNeeded(int capacity) {
      boolean currentAltHashing = hashSeed != 0;
      boolean useAltHashing = sun.misc.VM.isBooted() &&
              (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
      boolean switching = currentAltHashing ^ useAltHashing;
      if (switching) {
          hashSeed = useAltHashing
              ? sun.misc.Hashing.randomHashSeed(this)
              : 0;
      }
      return switching;
  }

当length为2的n次方时,h&(length – 1)就相当于对length取模,而且速度比直接取模快得多,这是HashMap在速度上的一个优化。简单的解释就是当length为2的n次方时,length-1的二进制为n个1,这样来做&运算得到的值差异化最大,hash冲突也就最少。
然后是阈值的计算,以及进行table初始化数组。
其中initHashSeedAsNeeded方法用于初始化hashSeed参数,其中hashSeed用于计算key的hash值,它与key的hashCode进行按位异或运算。这个hashSeed是一个与实例相关的随机值,主要用于解决hash冲突。

  private int hash(Object k) {
      int h = hashSeed;
      if (0 != h && k instanceof String) {
          return sun.misc.Hashing.stringHash32((String) k);
      }

      h ^= k.hashCode();

      // This function ensures that hashCodes that differ only by
      // constant multiples at each bit position have a bounded
      // number of collisions (approximately 8 at default load factor).
      h ^= (h >>> 20) ^ (h >>> 12);
      return h ^ (h >>> 7) ^ (h >>> 4);
  }

链地址法的可视化

网上找到个很好的网站,用来可视化各种常见的算法,很棒。瞬间觉得国外大学比国内的强不知多少倍。

下面的链接可以模仿哈希表采用链地址法解决冲突,大家可以自己去玩玩

集合遍历效率总结

l ArrayList是数组结构,ArrayList常用遍历有for循环(索引访问)、增强for循环、迭代器迭代。其中按索引访问效率最高,其次是增强for循环,使用迭代器的效率最低。

 

(1)按索引访问时间复杂度为O(1),即一次定位寻址即可。

(2)查找某一个值,需要遍历数组逐个对比,时间复杂度为O(n),即需要对比n次。

(3)对于二分查找(元素有序是前提)时间复杂度为O(logn)。

(4)对于插入和删除,因为涉及到元素移动的问题,时间复杂度也为O(n)。

 

l LinkedList是链表结构,常用遍历也有for循环(索引访问)、增强for循环、迭代器迭代。建议不要采用随机访问的方式去遍历LinkedList,而采用逐个遍历的方式。

 

(1)查找某一个值,需要遍历链表逐个对比,时间复杂度为O(n)。

(2)对于插入、删除等操作,由于只需要改变前后节点之间的指针,时间复杂度为O(1)。

 

l HashMap是“数组+链表”的结构。其遍历方式也很多,可以通过keyset遍历、通过entrySet遍历、通过Map.values()遍历(这种方式只能获得value)。

 

(1)如果table[i]处没有链表,对于查找一次定位,时间复杂度为O(1),对于增加、删除,本质上也是对链表的增加、删除(可以理解table[i]处是只有一个节点的链表),所以时间复杂度为O(1)。

(2)如果table[i]处有链表,查找时需要遍历链表,时间复杂度为O(n),增加、删除时间复杂度为O(1)。

 

l TreeMap是二叉树结构,可以通过keyset、entrySet等方式遍历。

 

(1)对于二叉树的遍历,给定某一个值,它会先和二叉树的root节点对比,如果值比root节点大则在右子树遍历,否则就在左子树遍历,以此类推。因此,对于查找、增加、删除等操作,都不会遍历完整棵树,平均复杂度均为O(logn)。

HashMap理解

  1. HashMap定义
  2. HashMap实现机制
  3. HashMap与HashTable的主要区别
  4. 关键属性
  5. 构造函数
  6. put和get方法
    6.1. 存储数据
    6.2. 扩容容
    6.3. 数据读取
  7. HashMap的性能参数

  8. <a name='HashMap-0'></a>HashMap定义


看下HashMap的定义:

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable

HashMap继承了AbstractMap<K,V>抽象类,提供了Map<K,V>接口骨干方法的实现。

This class provides a skeletal implementation of the <tt>Map</tt> interface, to minimize the effort required to implement this interface.

HashMap实现了Map<K,V>、Cloneable、Serializable接口。

  • 初始化哈希表时,容量为默认容量,阈值为 容量* 负载因子。
  • 已有哈希表扩容时,容量、阈值均翻倍。
  • 如果之前节点类型是树,需要把新哈希表表里当前桶也变成树形结构。
  • 复制到新哈希表时需要重新索引,这里采用的计算方法为e.hash() & (newCap - 1);等价于e.hash() % newCap可以发现扩容开销确实大,需要迭代所有元素,rehash、复制,还得保留原来的数据结构。所以应该尽量少扩容,最好在初始化的时候指定好HashMap的长度,尽量避免resize()。

葡京正网网投,设计理念(design concept)

Comparator与Comparable

在TreeMap的分析和举例中,我们提到了TreeMap中的元素排序比较采用的是Comparator接口的compare()方法和Comparable接口的compareTo()。当元素本身不具备比较性或者具备的比较性不满足我们的需求时,我们就可以使用Comparator接口或者Comparable接口来重写我们需要的比较逻辑。Comparator接口和Comparable接口实现比较的主要区别是:Comparator 是在元素外部实现的排序,这是一种策略模式,就是不改变元素自身,而用一个策略对象(自定义比较器)来改变比较行为。而Comparable接口则需要修改要比较的元素,让元素具有比较性,在元素内部重新修改比较行为。看下面的两个列子。

4. <a name='-3'></a>关键属性

  static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16  默认初始容量
  static final int MAXIMUM_CAPACITY = 1 << 30;    // 最大容量
  static final float DEFAULT_LOAD_FACTOR = 0.75f; // 默认初识加载因子为0.75
  transient int size; // 实际存储的key-value的数量
  int threshold;  // 临界值 当实际大小超过临界值时,会进行扩容threshold = 加载因子*容量
  transient int modCount; // 被修改的次数
  final float loadFactor; // 加载因子

其中loadFactor加载因子是表示Hash表中元素的填满的程度.
若:加载因子越大,填满的元素越多。好处是:空间利用率高了,但:冲突的机会加大了,冲突的机会越大,则查找的成本越高。
反之,加载因子越小,填满的元素越少,好处是:冲突的机会减小了,但:空间浪费多了.表中的数据将过于稀疏(很多空间还没用,就开始扩容了)链表长度会越来越长,查找效率降低。

如果机器内存足够,并且想要提高查询速度的话可以将加载因子设置小一点;相反如果机器内存紧张,并且对查询速度没有什么要求的话可以将加载因子设置大一点。不过一般我们都不用去设置它,让它取默认值0.75就好了。

在JDK8之后如果桶中的链表长度大于8之后,就会将其转换为一棵红黑树,目的在于能够提高查大量哈希冲突后的元素遍历。首先看一下HashMap中的红黑树定义:

AbstractMap抽象类

AbstractMapMap中的方法提供了一个基本实现,减少了实现Map接口的工作量。

举例来说:

如果要实现个不可变(unmodifiable)的map,那么只需继承AbstractMap,然后实现其entrySet方法,这个方法返回的set不支持add与remove,同时这个set的迭代器(iterator)不支持remove操作即可。

相反,如果要实现个可变(modifiable)的map,首先继承AbstractMap,然后重写(override)AbstractMap的put方法,同时实现entrySet所返回set的迭代器的remove方法即可。

小结

其实只要理解了集合体系各个主要实现类底层的数据结构类型,根据数据结构的特性,就能联想到该集合有什么特点,也很容易理解它们主要方法上的实现过程。文章主要介绍了常用的接口和实现类,还有很多没提到,通过集合框架图分模块记忆,整体把握,再根据需要扩展其它没提到的内容。

3. <a name='HashMapHashTable-2'></a>HashMap与HashTable的主要区别

  • 定义。HashMap实现了AbstractMap抽象类,而HashTable实现的是比较老的Dictionary抽象类.

  • 值存储。HashMap可以存储key为null、value为null的值,而HashTable不允许存储key为null或者value为null的值,会抛出NullPointerException异常。

  • 线程同步。HashMap是线程不安全的。HashTable是线程安全的,其方法包含synchronized关键字实现线程安全。

  • hash值计算。HashMap计算hash值:

  final int hash(Object k) {
      int h = hashSeed;
      if (0 != h && k instanceof String) {
          return sun.misc.Hashing.stringHash32((String) k);
      }

      h ^= k.hashCode();

      // This function ensures that hashCodes that differ only by
      // constant multiples at each bit position have a bounded
      // number of collisions (approximately 8 at default load factor).
      h ^= (h >>> 20) ^ (h >>> 12);
      return h ^ (h >>> 7) ^ (h >>> 4);
  }

HashTable计算hash值:

  private int hash(Object k) {
      // hashSeed will be zero if alternative hashing is disabled.
      return hashSeed ^ k.hashCode();
  }
  • 默认大小。HashMap默认数组大小为16,加载因子为0.75,重新hash阈值为12。
    HashTable默认数组大小为11,加载因子为0.75,重新hash阈值为8。

  • 扩容方式。HashMap中的数组容量大小始终保证为2的指数。重新hash,扩充容量方式为:当前容量大小*2。

    HashTable扩容方式为:int newCapacity = oldCapacity * 2 + 1。

  • 成员方法不同。Hashtable包含一些旧的方法,如contains方法。

//Set集合中Entry个数就是map中映射的个数 public int size() { return entrySet; } public boolean isEmpty() { //长度为0就是为空 return size() == 0; } public boolean containsValue(Object value) { //获取Entry的迭代器,然后通过Entry.getValue()来获取映射值 Iterator<Map.Entry<K,V>> i = entrySet().iterator(); //分是否为null进行判断 if (value==null) { while (i.hasNext { Map.Entry<K,V> e = i.next(); if (e.getValue return true; } } else { while (i.hasNext { Map.Entry<K,V> e = i.next(); if (value.equals(e.getValue return true; } } return false; } public boolean containsKey(Object key) { //获取Entry的迭代器,然后通过Entry.getKey来判断是否存在指定key Iterator<Map.Entry<K,V>> i = entrySet().iterator(); //通过这里来看可以知道,Map中的key是允许为null的。 if (key==null) { while (i.hasNext { Map.Entry<K,V> e = i.next(); if (e.getKey return true; } } else { while (i.hasNext { Map.Entry<K,V> e = i.next(); if (key.equals(e.getKey return true; } } return false; } public V get(Object key) { //获取Entry的迭代器 Iterator<Map.Entry<K,V>> i = entrySet().iterator(); if (key==null) { while (i.hasNext { Map.Entry<K,V> e = i.next(); if (e.getKey return e.getValue(); } } else { while (i.hasNext { Map.Entry<K,V> e = i.next(); //通过key的equals来比较key是否相同 if (key.equals(e.getKey return e.getValue(); } } //如果没有找到,则返回null return null; } public V remove(Object key) { Iterator<Map.Entry<K,V>> i = entrySet().iterator(); Map.Entry<K,V> correctEntry = null; //查找要删除的Entry if (key==null) { while (correctEntry==null && i.hasNext { Map.Entry<K,V> e = i.next(); if (e.getKey correctEntry = e; } } else { while (correctEntry==null && i.hasNext { Map.Entry<K,V> e = i.next(); if (key.equals(e.getKey correctEntry = e; } } //存储要删除的value,如果没有找到要删除的映射,则返回null。找到的话则返回删除key对应的value。 V oldValue = null; if (correctEntry !=null) { oldValue = correctEntry.getValue(); i.remove(); } return oldValue; } public void putAll(Map<? extends K, ? extends V> m) { //遍历指定的map,然后调用put方法。 for (Map.Entry<? extends K, ? extends V> e : m.entrySet put(e.getKey(), e.getValue; } public void clear() { //直接使用Set的clear()方法 entrySet; } public Set<K> keySet() { //如果key为空,则返回一个空的set集合 if (keySet == null) { keySet = new AbstractSet<K>() { //AbstractSet中的抽象方法iterator方法实现 public Iterator<K> iterator() { return new Iterator<K>() { //直接使用entrySet的迭代器 private Iterator<Map.Entry<K,V>> i = entrySet().iterator(); public boolean hasNext() { return i.hasNext(); } public K next() { return i.next().getKey(); } public void remove() { i.remove(); } }; } public int size() { return AbstractMap.this.size(); } public boolean isEmpty() { return AbstractMap.this.isEmpty(); } public void clear() { AbstractMap.this.clear(); } public boolean contains { return AbstractMap.this.containsKey; } }; } return keySet; } public Collection<V> values() { //如果值集合为空,则返回一个新建的Collection if (values == null) { values = new AbstractCollection<V>() { public Iterator<V> iterator() { return new Iterator<V>() { private Iterator<Map.Entry<K,V>> i = entrySet().iterator(); public boolean hasNext() { return i.hasNext(); } public V next() { return i.next().getValue(); } public void remove() { i.remove(); } }; } public int size() { return AbstractMap.this.size(); } public boolean isEmpty() { return AbstractMap.this.isEmpty(); } public void clear() { AbstractMap.this.clear(); } public boolean contains { return AbstractMap.this.containsValue; } }; } return values; }

HashMap.Entry

HashMap中存放的是HashMap.Entry对象,它继承自Map.Entry,其比较重要的是构造函数

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;
    int hash;
    Entry(int h, K k, V v, Entry<K,V> n) {
        value = v;
        next = n;
        key = k;
        hash = h;
    }
    // setter, getter, equals, toString 方法省略
    public final int hashCode() {
        //用key的hash值与上value的hash值作为Entry的hash值
        return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
    }
    /**
     * This method is invoked whenever the value in an entry is
     * overwritten by an invocation of put(k,v) for a key k that's already
     * in the HashMap.
     */
    void recordAccess(HashMap<K,V> m) {
    }
    /**
     * This method is invoked whenever the entry is
     * removed from the table.
     */
    void recordRemoval(HashMap<K,V> m) {
    }
}

可以看到,Entry实现了单向链表的功能,用next成员变量来级连起来。

介绍完Entry对象,下面要说一个比较重要的成员变量

/**
 * The table, resized as necessary. Length MUST Always be a power of two.
 */
//HashMap内部维护了一个为数组类型的Entry变量table,用来保存添加进来的Entry对象
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

你也许会疑问,Entry不是单向链表嘛,怎么这里又需要个数组类型的table呢?

我翻了下之前的算法书,其实这是解决冲突的一个方式:链地址法(开散列法),效果如下:

葡京正网网投 9

链地址法处理冲突得到的散列表

就是相同索引值的Entry,会以单向链表的形式存在

Map接口

不同于List和Set,集合体系中的Map是“双列集合”,存储的是内容是键值对(key-value),Map集合的特点是不能包含重复的键,每一个键最多能映射一个值。Map接口抽象出了基本的增删改查操作。定义如下:

public interface Map<K,V> {}

主要方法

/**添加**/
V put(K key, V value);
void putAll(Map<? extends K, ? extends V> m);

/**删除**/
void clear();
V remove(Object key);

/**判断**/
boolean isEmpty();
boolean containsKey(Object key);
boolean containsValue(Object value);

/**获取**/
int size();
V get(Object key);
Collection<V> values();
Set<K> keySet();
Set<Map.Entry<K, V>> entrySet();

Map接口的主要实现类有HashMap和TreeMap。

6.3. <a name='-8'></a>数据读取

  public V get(Object key) {
      if (key == null)
          return getForNullKey();
      Entry<K,V> entry = getEntry(key);

      return null == entry ? null : entry.getValue();
  }

有了上面存储时的hash算法作为基础,理解起来这段代码就很容易了。从上面的源代码中可以看出:从HashMap中get元素时,首先计算key的hashCode,找到数组中对应位置的某一元素,然后通过key的equals方法在对应位置的链表中找到需要的元素。

static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode ^ (h >>> 16); }

remove操作

public V remove(Object key) {
    Entry<K,V> e = removeEntryForKey(key);
    //可以看到删除的key如果存在,就返回其所对应的value
    return (e == null ? null : e.value);
}
final Entry<K,V> removeEntryForKey(Object key) {
    if (size == 0) {
        return null;
    }
    int hash = (key == null) ? 0 : hash(key);
    int i = indexFor(hash, table.length);
    //这里用了两个Entry对象,相当于两个指针,为的是防治冲突链发生断裂的情况
    //这里的思路就是一般的单向链表的删除思路
    Entry<K,V> prev = table[i];
    Entry<K,V> e = prev;
    //当table[i]中存在冲突链时,开始遍历里面的元素
    while (e != null) {
        Entry<K,V> next = e.next;
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k)))) {
            modCount++;
            size--;
            if (prev == e) //当冲突链只有一个Entry时
                table[i] = next;
            else
                prev.next = next;
            e.recordRemoval(this);
            return e;
        }
        prev = e;
        e = next;
    }
    return e;
}

到现在为止,HashMap的增删改查都介绍完了。
一般而言,认为HashMap的这四种操作时间复杂度为O(1),因为它hash函数性质较好,保证了冲突发生的几率较小。

ArrayList

ArrayList是List接口的一个具体的实现类。ArrayList的底层数据结构是数组结构,相当于一个动态数组。ArrayList的特点是随机查询速度快、增删慢、线程不安全。ArrayList和Vector的区别是:Vector是线程安全的(synchronized实现)。定义如下:

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{}

l ArrayList 继承AbstractList,AbstractList是对一些公有操作的再次抽象,抽出一些特性操作,如根据索引操作元素,生产迭代器等。

l ArrayList 实现了RandmoAccess接口,即提供了随机访问功能,可以通过元素的索引快速获取元素对象。

l ArrayList 实现了Cloneable接口,即覆盖了函数clone(),能被克隆。

l ArrayList 实现java.io.Serializable接口,这意味着ArrayList支持序列化,能通过序列化去传输。

 

ArrayList源码分析总结(源码略,建议先整体认识再打开源码对着看):

 

l 可以通过构造函数指定ArrayList的容量大小,若不指定则默认是10。

l 添加新元素时,容量不足以容纳全部元素时,会重新创建一个新的足以容纳全部元素的数组,把旧数组中的元素拷贝到新的数组中并返回新的数组。增量具体看源码。

l 添加的新元素添加到数组末尾。

l 查找、删除元素使用equals方法比较对象。

l ArrayList的克隆函数,即是将全部元素克隆到一个数组中。

l ArrayList的序列化,即通过java.io.ObjectOutputStream将ArrayList的长度和每一个元素写到输出流中,或者通过java.io.ObjectInputStream从输入流中读出长度和每一个元素到一个数组中。

  • Attributes:Attributes实现了Map接口,它将Manifest属相映射到关联的字符串,底层使用Map实现key-value存储。
  • HashTable:继承Dictionary类,并且实现了Map接口。线程安全的哈希表实现,实现方式和HashMap类似采用数组实现存储,采用链表解决hash冲突(没有提供红黑树的优化)。HashTable通过为每个方法增加synchronized同步锁的方式,保证线程安全。如果不需要线程安全建议使用HashMap,如果需要线程安全,并且对高并发有要求,建议使用ConcurrentHashMap。
  • ConcurrentHashMap:功能和HashTable一样,但是不是通过锁来来保证方法访问的线程安全,所以能够应对高并发下的使用。ConcurrentHashMap采用的是锁分段技术,将数据分成一段段的存储,然后给每一段分配一把锁,当线程占用锁访问其中一段数据时,其它端还能够被访问。
  • LinkedHashMap:LinkedHashMap继承了HashMap和Map接口,它与HashMap不同的是将所有元素通过一个双向链表连接。这样就提供了可以按照插入顺序遍历元素的可能,而不需要使用TreeMap那样引入额外成本。LinkedHashMap提供了一个特殊构造函数,其迭代顺序为其元素最后一次访问的顺序,这个非常适合构建LRU缓存。
  • EnumMap:专门用于枚举类型键的Map实现,枚举映射中的所有键必须来创建映射时指定的枚举类型。
  • IdentityHashMap:不是通用Map的实现,因为它违反了Map的规定,它要求在比较对象时使用equals方法。此类仅在引用相等语义的情况下使用。
  • Properties:继承HashTable,Properties类表示一组持久的属性,可以将Properties保存到流中,会从流中加载。Properties中每个键和值都是一个字符串。
  • WeakHashMap:WeakHashMap继承AbstractMap,并且实现了Map接口。WeakHashMap和HashMap类似,但是WeakHashMap中键为弱键,意思是当键不在正常使用时,会被从WeakHashMap中自动移除。比如WeakHashMap中键没有其它对象引用使用时,就会被GC回收。
  • ConcurrentSkipListMap

签名(signature)

public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable

可以看到HashMap葡京网投哪个正规,继承了

  • 标记接口Cloneable,用于表明HashMap对象会重写java.lang.Object#clone()方法,HashMap实现的是浅拷贝(shallow copy)。
  • 标记接口Serializable,用于表明HashMap对象可以被序列化

比较有意思的是,HashMap同时继承了抽象类AbstractMap与接口Map,因为抽象类AbstractMap的签名为

public abstract class AbstractMap<K,V> implements Map<K,V>

Stack Overfloooow上解释到:

在语法层面继承接口Map是多余的,这么做仅仅是为了让阅读代码的人明确知道HashMap是属于Map体系的,起到了文档的作用

AbstractMap相当于个辅助类,Map的一些操作这里面已经提供了默认实现,后面具体的子类如果没有特殊行为,可直接使用AbstractMap提供的实现。

ArrayList保证唯一性

List中的元素是可以重复的,可以通过重写equals方法实现唯一性。下面是ArrayList实现元素去重(依据equals)的一个例子。

 

葡京正网网投 10葡京正网网投 11

class Teacher {
    private String name;
    private String age;

    Teacher(String name,String age) {
        this.name = name;
        this.age = age;
    }
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public String getAge() {
        return age;
    }
    public void setAge(String age) {
        this.age = age;
    }
    @Override
    public boolean equals(Object obj) {
        if(!(obj instanceof Teacher)) {
            return false;
        }
        Teacher p = (Teacher)obj;
        System.out.println("调用equals比较" + p.name + "与" + this.name);
        return p.name.equals(this.name) && p.age.equals(this.age);
    }
}

public class ArrayListDuplicate {

    public static void main(String[] args) {
        ArrayList al = new ArrayList();
        al.add(new Teacher("zhangsan","20"));
        al.add(new Teacher("lingsi","21"));
        al.add(new Teacher("wangwu","22"));
        al.add(new Teacher("wangwu","22"));

        print("-----------原始ArrayList----------");

        Iterator it = al.iterator();
        while(it.hasNext()) {
            Teacher obj = (Teacher)it.next();
            print(obj.getName() + "-" + obj.getAge());
        }

        print("-----------删除重复元素----------");
        ArrayList al2 = removeSameObj(al);

        Iterator it2 = al2.iterator();
        while(it2.hasNext()) {
            Teacher obj = (Teacher)it2.next();
            print(obj.getName() + "-" + obj.getAge());
        }

        print("-----------删除lingsi元素----------");
        al2.remove(new Teacher("lingsi","21"));

        Iterator it3 = al2.iterator();
        while(it3.hasNext()) {
            Teacher obj = (Teacher)it3.next();
            print(obj.getName() + "-" + obj.getAge());
        }

    }

    public static ArrayList removeSameObj(ArrayList al) {
        ArrayList newAl = new ArrayList();
        Iterator it = al.iterator();
        while(it.hasNext()) {
            Object obj = it.next();
            if(!newAl.contains(obj)) {
                newAl.add(obj);
            }
        }
        return newAl;
    }

    public static void print(Object obj) {
        System.out.println(obj);
    }

}

运行结果:
-----------原始ArrayList----------
zhangsan-20
lingsi-21
wangwu-22
wangwu-22
-----------删除重复元素----------
调用equals比较zhangsan与lingsi
调用equals比较zhangsan与wangwu
调用equals比较lingsi与wangwu
调用equals比较zhangsan与wangwu
调用equals比较lingsi与wangwu
调用equals比较wangwu与wangwu
zhangsan-20
lingsi-21
wangwu-22
-----------删除lingsi元素----------
调用equals比较zhangsan与lingsi
调用equals比较lingsi与lingsi
zhangsan-20
wangwu-22

View Code

从运行结果中可以看出,调用list的contains方法和remove方法时,调用了equals方法进行比较(List集合中判断元素是否相等依据的是equals方法)

 

葡京正网网投 12image.png

HashMap的序列化

介绍到这里,基本上算是把HashMap中一些核心的点讲完了,但还有个比较严重的问题:保存Entry的table数组为transient的,也就是说在进行序列化时,并不会包含该成员,这是为什么呢?

transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;

为了解答这个问题,我们需要明确下面事实:

  • Object.hashCode方法对于一个类的两个实例返回的是不同的哈希值

我们可以试想下面的场景:

我们在机器A上算出对象A的哈希值与索引,然后把它插入到HashMap中,然后把该HashMap序列化后,在机器B上重新算对象的哈希值与索引,这与机器A上算出的是不一样的,所以我们在机器B上get对象A时,会得到错误的结果。

所以说,当序列化一个HashMap对象时,保存Entry的table是不需要序列化进来的,因为它在另一台机器上是错误的。

因为这个原因,HashMap重现了writeObjectreadObject 方法

private void writeObject(java.io.ObjectOutputStream s)
    throws IOException
{
    // Write out the threshold, loadfactor, and any hidden stuff
    s.defaultWriteObject();

    // Write out number of buckets
    if (table==EMPTY_TABLE) {
        s.writeInt(roundUpToPowerOf2(threshold));
    } else {
       s.writeInt(table.length);
    }

    // Write out size (number of Mappings)
    s.writeInt(size);

    // Write out keys and values (alternating)
    if (size > 0) {
        for(Map.Entry<K,V> e : entrySet0()) {
            s.writeObject(e.getKey());
            s.writeObject(e.getValue());
        }
    }
}

private static final long serialVersionUID = 362498820763181265L;

private void readObject(java.io.ObjectInputStream s)
     throws IOException, ClassNotFoundException
{
    // Read in the threshold (ignored), loadfactor, and any hidden stuff
    s.defaultReadObject();
    if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
        throw new InvalidObjectException("Illegal load factor: " +
                                           loadFactor);
    }

    // set other fields that need values
    table = (Entry<K,V>[]) EMPTY_TABLE;

    // Read in number of buckets
    s.readInt(); // ignored.

    // Read number of mappings
    int mappings = s.readInt();
    if (mappings < 0)
        throw new InvalidObjectException("Illegal mappings count: " +
                                           mappings);

    // capacity chosen by number of mappings and desired load (if >= 0.25)
    int capacity = (int) Math.min(
                mappings * Math.min(1 / loadFactor, 4.0f),
                // we have limits...
                HashMap.MAXIMUM_CAPACITY);

    // allocate the bucket array;
    if (mappings > 0) {
        inflateTable(capacity);
    } else {
        threshold = capacity;
    }

    init();  // Give subclass a chance to do its thing.

    // Read the keys and values, and put the mappings in the HashMap
    for (int i = 0; i < mappings; i++) {
        K key = (K) s.readObject();
        V value = (V) s.readObject();
        putForCreate(key, value);
    }
}
private void putForCreate(K key, V value) {
    int hash = null == key ? 0 : hash(key);
    int i = indexFor(hash, table.length);

    /**
     * Look for preexisting entry for key.  This will never happen for
     * clone or deserialize.  It will only happen for construction if the
     * input Map is a sorted map whose ordering is inconsistent w/ equals.
     */
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k)))) {
            e.value = value;
            return;
        }
    }

    createEntry(hash, key, value, i);
}

简单来说,在序列化时,针对Entry的key与value分别单独序列化,当反序列化时,再单独处理即可。

集合框架图

集合既然能存储不同类型的的对象,那么集合体系中肯定有不同类型的容器,集合中主要有List、Set、Map三种容器,每种容器的数据结构都不一样。集合体系的类、接口非常多,方便记忆,我们将下面这个相对简洁的集合框架图分为从5个模块来学习:

1.Collection集合

2.Map集合

3.集合遍历

4.集合比较

5.集合工具类

 

葡京正网网投 13 

先对图做一下解析:

l 点线框表示接口

l 实现框表示具体的类

l 带有空心箭头的点线表示一个具体的类实现了一个接口

l 实心箭头表示某一个类可以生成箭头所指向的类

l 常用的容器用黑色粗线表示

 

LinkedHashSet继承HashSet,它主要使用了HastSet的最后一个构造方法,创建LinkedHashMap。所以LinkedHashSet底层采用的LinkedHashMap进行操作。

哈希表(hash table)

HashMap是一种基于哈希表(hash table)实现的map,哈希表(也叫关联数组)一种通用的数据结构,大多数的现代语言都原生支持,其概念也比较简单:key经过hash函数作用后得到一个槽(buckets或slots)的索引(index),槽中保存着我们想要获取的值,如下图所示

葡京正网网投 14

hash table demo

很容易想到,一些不同的key经过同一hash函数后可能产生相同的索引,也就是产生了冲突,这是在所难免的。
所以利用哈希表这种数据结构实现具体类时,需要:

  • 设计个好的hash函数,使冲突尽可能的减少
  • 其次是需要解决发生冲突后如何处理。

后面会重点介绍HashMap是如何解决这两个问题的。

集合比较

AbstractMap是Map接口的核心实现抽象类,这样以后map就不需要重新实现这些方法了。当我们要实现一个不可变Map时,可以直接继承该抽象类。如果想要实现可变的Map映射,则还需要覆盖put方法。因为AbstractMap中定义的put方法是不允许操作的。

Map接口

在Eclipse中的outline面板可以看到Map接口里面包含以下成员方法与内部类:

葡京正网网投 15

Map_field_method

可以看到,这里的成员方法不外乎是“增删改查”,这也反映了我们编写程序时,一定是以“数据”为导向的。

在上篇文章讲了Map虽然并不是Collection,但是它提供了三种“集合视角”(collection views),与下面三个方法一一对应:

  • Set<K> keySet(),提供key的集合视角
  • Collection<V> values(),提供value的集合视角
  • Set<Map.Entry<K, V>> entrySet(),提供key-value序对的集合视角,这里用内部类Map.Entry表示序对

TreeMap举例

葡京正网网投 16葡京正网网投 17

public class TreeMapTest {

    public static void main(String[] args) {
        System.out.println("---TreeMap默认按key升序排序---");
        TreeMap<Integer,String> map = new TreeMap<Integer,String>();
        map.put(200,"sha");
        map.put(300,"can");
        map.put(100,"pek");
        map.put(400,"szx");

        Set<Entry<Integer,String>> se = map.entrySet();
        Iterator<Entry<Integer,String>> it = se.iterator();
        while(it.hasNext()) {
            Entry<Integer,String> en = (Entry<Integer,String>)it.next();
            System.out.println(en.getKey() + "-" + en.getValue());
        }

        System.out.println("---TreeMap使用自定义比较器降序排序---");
        TreeMap<Integer,String> map2 = new TreeMap<Integer,String>(new                         CityNumComparator());
        map2.put(200,"sha");
        map2.put(300,"can");
        map2.put(100,"pek");
        map2.put(400,"szx");

        Set<Entry<Integer,String>> se2 = map2.entrySet();
        Iterator<Entry<Integer,String>> it2 = se2.iterator();
        while(it2.hasNext()) {
            Entry<Integer,String> en = (Entry<Integer,String>)it2.next();
            System.out.println(en.getKey() + "-" + en.getValue());
        }

    }
}

class CityNumComparator implements Comparator {
    @Override
    public int compare(Object o1, Object o2) {
        if(!(o1 instanceof Integer) || !(o2 instanceof Integer)) {
            throw new RuntimeException("不可比较的对象");
        }
        Integer num1 = (Integer)o1;
        Integer num2 = (Integer)o2;

        if(num1 < num2) {
            return 1;
        }
        if(num1 > num2) {
            return -1;
        }
        return 0;
        //Integer类型自身已经自有比较性,或者
        //return num2.compareTo(num1);
    }
} 

运行结果:
---TreeMap默认按key升序排序---
100-pek
200-sha
300-can
400-szx
---TreeMap使用自定义比较器降序排序---
400-szx
300-can
200-sha
100-pek

View Code

由此可见,要想按照自己的方式对TreeMap进行排序,可以自定义比较器重写compare()方法重写自己的比较逻辑。

首先TreeMap的构造方法就是包含了第一开始所说的可排序Map四类构造函数。

get操作

get操作相比put操作简单,所以先介绍get操作

public V get(Object key) {
    //单独处理key为null的情况
    if (key == null)
        return getForNullKey();
    Entry<K,V> entry = getEntry(key);
    return null == entry ? null : entry.getValue();
}
private V getForNullKey() {
    if (size == 0) {
        return null;
    }
    //key为null的Entry用于放在table[0]中,但是在table[0]冲突链中的Entry的key不一定为null
    //所以需要遍历冲突链,查找key是否存在
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null)
            return e.value;
    }
    return null;
}
final Entry<K,V> getEntry(Object key) {
    if (size == 0) {
        return null;
    }
    int hash = (key == null) ? 0 : hash(key);
    //首先定位到索引在table中的位置
    //然后遍历冲突链,查找key是否存在
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
         e != null;
         e = e.next) {
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}

集合遍历

public Iterator<E> iterator() { //返回map key的迭代器 return map.keySet().iterator(); } public int size() { //返回map个数 return map.size(); } public boolean isEmpty() { //判断map是否为空 return map.isEmpty(); } public boolean contains { //判断map的是否包含指定key return map.containsKey; } public boolean add { //将添加值作为map的key存储 return map.put(e, PRESENT)==null; } public boolean remove { return map.remove==PRESENT; } public void clear() { map.clear(); } public Spliterator<E> spliterator() { return new HashMap.KeySpliterator<E,Object>(map, 0, -1, 0, 0); }

总结

在总结完HashMap后,发现这里面一些核心的东西,像哈希表的冲突解决,都是算法课上学到,不过由于“年代久远”,已经忘得差不多了,我觉得忘

  • 一方面是由于时间久不用
  • 另一方面是由于本身没理解好

平时多去思考,这样在遇到一些性能问题时也好排查。

还有一点就是我们在分析某些具体类或方法时,不要花太多时间一些细枝末节的边界条件上,这样很得不偿失,倒不是说这么边界条件不重要,程序的bug往往就是边界条件没考虑周全导致的。

只是说我们可以在理解了这个类或方法的总体思路后,再来分析这些边界条件。

如果一开始就分析,那真是丈二和尚——摸不着头脑了,随着对它工作原理的加深,才有可能理解这些边界条件的场景。

Arrays

Arrays也是一个工具类,提供了操作数组以及在数组和集合之间转换的一些常用方法。

/**可以对各种类型的数组进行排序**/
void sort(Object[] a)

/** 数组变集合**/
<T> List<T> asList(T... a)

/** 数组转成字符串**/
String toString(Object[] a)

葡京正网网投 18image.png

LinkedList

LinkedList是List接口的一个具体的实现类。LinkedList底层数据结构是双向的链表结构,可以当成堆栈或者队列来使用。LinkedList的特点是增删速度很快,顺序查询效率较高,随机查询稍慢。定义如下:

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{} 

l LinkedList 是继承AbstractSequentialList,AbstractSequentialList是AbstractList的一个子类。

l LinkedList 实现 Deque 接口,即能将LinkedList当作双端队列使用。

l 同ArrayList,LinkedList同样支持克隆和序列化。

 

LinkedList 源码分析总结(源码略,建议先整体认识再打开源码对着看):

 

l LinkedList的本质是一个双向链表,各有一个头节点和尾节点,每一个节点都有个数据域、一个指向上一个节点的指针域、一个指向上下一个节点的指针域。

l 添加元素时,将元素添加到双向链表的末端。

l 查找、删除元素时,使用equals方法比较对象。

l 根据索引查找元素时,若索引值index < 双向链表长度的1/2,则从表头往后查找,否则从表尾往前找。

l LinkedList的克隆和序列化原理同ArrayList。

l LinkedList实现了Deque,Deque接口定义了在双端队列两端访问元素的方法,每种方法都存在两种形式:一种是在操作失败时抛出异常,另一种是返回一个特殊值(null 或 false)。

l LinkedList有自己特有的迭代器ListIterator。

l LinkedList不存在扩容增量的问题。

  1. 哈希表中的链表数组。

List接口

List是Collection的一个子接口,List中的元素是有序的,可以重复,有索引。

定义如下:

public interface List<E> extends Collection<E> {}

葡京正网网投 19 

 

List是继承于Collection接口,它自然就包含了Collection中的全部函数接口,由于List有自己的特点(素是有序的,可以重复,有索引),因此List也有自己特有的一些操作,如上红色框框中的。List特有的操作主要是带有索引的操作和List自身的迭代器(如上图)。List接口的常用实现类有ArrayList和LinkedList。

 

  1. 最大容量2^30,所以map大小为2 ~ 2^30 中间的偶数个。

千里之行,始于足下。把别人的变成自己,再把自己的分享给别人,这也是一次提升的过程。本文的目的是以一篇文章从整体把握集合体系又不失一些细节上的实现,高手路过。

注意这里提供了许多NavigableSet中定义的匹配检索最近元素的方法,比如taiSet、subSet、headSet等。TreeSet底层实现方式和HashSet一样,直接操作的TreeMap。

TreeSet

TreeSet是Set接口的一个具体的实现类。其特点是元素是有序的,不可以重复。定义如下:

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable
{}

l TreeSet继承AbstractSet,AbstractSet抽象了equals()、hashCode()、removeAll()三个方法。

l TreeMap实现了NavigableMap接口,支持一系列的导航方法,比如返回有序的key集合。

l TreeSet实现了Cloneable,Serializable接口以便支持克隆和序列化。

l TreeSet保证元素唯一性依赖Comparator接口和Comparable接口。

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

TreeMap

TreeMap是Map接口的一个实现类,因此它存储的也是键值对(key-value)。TreeMap的底层数据结构是二叉树(红黑树),其特点是可以对元素进行排序,TreeMap是线程不安全的。定义如下:

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{}

l TreeMap继承AbstractMap,AbstractMap抽象了Map集合的一些基本操作。

l TreeMap实现了NavigableMap接口,支持一系列的导航方法,比如返回有序的key集合。

l TreeMap实现了Cloneable,Serializable接口以便支持克隆和序列化。

 

TreeMap源码分析总结(源码略,建议先整体认识再打开源码对着看):

 

l TreeMap的几个重要成员:root, size, comparator。

(1)root是红黑树的根节点,它是Entry类型,Entry是红黑数的节点,它包含了红黑数的6个基本组成成分:key(键)、value(值)、left(左孩子)、right(右孩子)、parent(父节点)、color(颜色)。Entry节点根据key进行排序,Entry节点包含的内容为value。

(2)comparator是比较器,使红黑树的节点具有比较性,用来给TreeMap排序。红黑数排序时,根据Entry中的key进行排序,Entry中的key比较大小是根据比较器comparator来进行判断的。

(3)size是红黑树节点的个数。

 

l TreeMap(Comparator<? super K> comparator)。带比较器的构造函数可以在TreeMap外部自定义TreeMap元素(红黑树节点)的比较器。

l get(Object key)。若比较器comparator不为空(即通过构造函数外部传入的),则通过Comparator接口的compare()方法从根节点开始和key逐个比较直到找出相等的节点。若比较器为空,则使用Comparable接口的compareTo()比较查找。

l put(K key, V value)。若根节点root为空,则根据key-value创建一个Entry对象插入到根节点。否则在红黑树中找到找到(key, value)的插入位置。查找插入位置还是若比较器comparator不为空则通过Comparator接口的compare()方法比较查找,否则通过Comparable接口的compareTo()方法比较查找。过程比较复杂。

l putAll(Map<? extends K, ? extends V> map)。调用AbstractMap中的putAll(),AbstractMap中的putAll()又会调用到TreeMap的put()。

l remove(Object key)。先根据key查找出对应的Entry,从红黑树中删除对应的Entry节点。

l clear()。clear把根节点设置为null即可。

l containsKey(Object key)。判断是否是包含该key的元素,查找方法同get()。

 

所有实现可排序的Map的实现类,都应该实现四个标准构造方法。

HashSet

HashSet是Set接口的一个具体的实现类。其特点是元素是无序的(取出顺序和存入顺序不一定一样),不可以重复。定义如下:

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{}

l HashSet继承AbstractSet,AbstractSet抽象了equals()、hashCode()、removeAll()三个方法。

l HashSet实现了Cloneable,Serializable接口以便支持克隆和序列化。

l HashSet保证元素唯一性依赖equals()方法和hashCode()方法。

 

首先我们看下红黑树的数据结构:

LinkedList实现堆栈和队列

LinkedList可以当成堆栈和队列使用,因为实现了Deque接口,Deque接口提供了一些了出栈入栈和出队入队的方法。

葡京正网网投 20葡京正网网投 21

class MyQueueStack {

    private LinkedList link;

    MyQueueStack() {
        link = new LinkedList();
    }

    public void add(Object obj) {
        link.addFirst(obj);
    }

    public Object remove() {
        //return link.removeLast();//队列
        return link.removeFirst();//栈
    }

    public boolean isNull() {
        if(!link.isEmpty()) {
            return false;
        }
        return true;
    }

}

public class LinkedListQueueStack {
    public static void main(String[] args) {
        MyQueueStack q = new MyQueueStack();
        q.add("001");
        q.add("002");
        q.add("003");

        while(!q.isNull())
            System.out.println(q.remove());
    }
}

队列运行结果:
001
002
003
栈运行结果:
003
002
001

View Code

除了上面说的Set,Java还提供了一下基类Set。CopyOnWriteArraySet,它底层采用CopyOnWriteArrayList实现。它是线程安全的Set,它适合用于小数据量集合,并且读操作远远超过修改操作,因为修改操作代价很昂贵,需要复制数组。用于枚举操作的EnumSet,EnumSet保证值存储单个枚举类型的元素。EnumSet底层使用Enum变量存储数据final Enum<?>[] universe;。EnumSet是抽象类,它主要被用于JumboEnumSet和RegularEnumSet。基于ConcurrentSkipListMap的实现的NavigableSet的实现类ConcurrentSkipListSet,它是线程安全的,并且元素有序。

让元素具有比较性

葡京正网网投 22葡京正网网投 23

//实现Comparable接口强制让Passenger对象具有可比性
class Passenger implements Comparable {
    private String name;
    private int age;

    Passenger(String name,int age) {
        this.name = name;
        this.age = age;
    }
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public int getAge() {
        return age;
    }
    public void setAge(int age) {
        this.age = age;
    }
    @Override
    public int compareTo(Object obj) {
        if(!(obj instanceof Passenger)) {
            return -1;
        }
        Passenger p = (Passenger)obj;
         System.out.println("调用compareTo比较"+ p.name + "与" + this.name);
        if(this.age> p.age) {
            return 1;
        }
        if(this.age == p.age) {
            return this.name.compareTo(p.name);
        }
        return -1;
    }
}

public class TreeSetTest {
    public static void main(String[] args) {
        TreeSet ts = new TreeSet();
         print("-----------添加元素到TreeSet----------");
        ts.add(new Passenger("zhangsan",20));
        ts.add(new Passenger("lingsi",21));
        ts.add(new Passenger("wangwu",22));
        ts.add(new Passenger("wangwu",22));

        Iterator it = ts.iterator();
        while(it.hasNext()) {
            Passenger obj = (Passenger)it.next();
            print(obj.getName() + "-" + obj.getAge());
        }
    }

    public static void print(Object obj) {
        System.out.println(obj);
    }
}

运行结果:
-----------添加元素到TreeSet----------
调用compareTo比较zhangsan与zhangsan
调用compareTo比较zhangsan与lingsi
调用compareTo比较zhangsan与wangwu
调用compareTo比较lingsi与wangwu
调用compareTo比较lingsi与wangwu
调用compareTo比较wangwu与wangwu
zhangsan-20
lingsi-21
wangwu-22

View Code

 

上面的例子中,Passenger本身并不具备比较性,但是通过修改Passenger,让其实现了Comparable 接口重写了compareTo()方法让其根据年龄具有比较性。

//将指定kv添加到Map中 public V put(K key, V value) { //需要先调用hash方法计算hash值 return putVal, key, value, false, true); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { //哈希表的一个引用 HashMap.Node<K,V>[] tab; //插入kv的节点 HashMap.Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize.length; //如果插入位置为空,则新建一个链表节点 if ((p = tab[i =  & hash]) == null) tab[i] = newNode(hash, key, value, null); else { //如果插入位置不为空则有两种情况:插入key已经存在或该key是产生hash冲途的链表内 HashMap.Node<K,V> e; K k;//e为当前插入节点 //拿出链表的第一个节点进行匹配,如果匹配成功则直接返回给e(对于引用类型需要使用equals比较,基础类型使用==比较) if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals e = p; //如果第一个节点不为目标节点,并且该节点类型是树形则新增节点到树中 else if (p instanceof HashMap.TreeNode) e = ((HashMap.TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { //遍历链表 for (int binCount = 0; ; ++binCount) { //如果遍历到最后,则直接将新节点添加到链表后面 if ((e = p.next) == null) { //新节点 p.next = newNode(hash, key, value, null); //当链表中节点个数大于8时,就需要树型化,提高效率 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } //如果匹配到则直接停止,此时e已经指向了对应节点 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals break; p = e; } } //替换旧节点 if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess; return oldValue; } } //记录修改次数 ++modCount; //如果超过阈值则进行扩容 if (++size > threshold) resize(); afterNodeInsertion; return null; }

Map集合

List应用举例

  • hash():计算哈希值,也就是数组中对应的位置
  • resize():扩容
  • putTreeVal():向树型节点添加元素
  • treeIfByBin():树形化容器

迭代器的设计原理

在上面List和Map的分析和举例中,已经提到迭代器了。因为每一种容器的底层数据结构不同,所以迭代的方式也不同,但是也有共同的部分,把这些共同的部分再次抽象,Iterator接口就是迭代器的顶层抽象。

 

List集合中有自己特有的迭代器ListIterator,ListIterator接口是Iterator接口的子接口。实现类ArrayList和LinkedList中有迭代器的具体实现(内部类)。把迭代器设计在集合的内部,这样,迭代器就可以轻松的访问集合的成员了。

private class ListItr extends Itr implements ListIterator<E>{}

而在HashMap和TreeMap的遍历中,我们经常将Map的键存到Set集合中,Set属于List的子接口,当然也继承了List特有的迭代器,通过迭代key来获取value。另一种方式是将Map中的映射关系Entry取出存储到Set集合,通过迭代每一个映射Entry关系获取Entry中的key和value。可以说,Map是借List的迭代器实现了对自身的遍历。

  1. 默认初始容量16,比如为2的整数倍

自定义比较器

葡京正网网投 24葡京正网网投 25

public class TreeSetTest2 {

    public static void main(String[] args) {
        TreeSet ts = new TreeSet(new MyComparator());
         print("-----------添加元素到TreeSet----------");
        ts.add(new Passenger("zhangsan",20));
        ts.add(new Passenger("lingsi",21));
        ts.add(new Passenger("wangwu",22));
        ts.add(new Passenger("chenliu",23));

        Iterator it = ts.iterator();
        while(it.hasNext()) {
            Passenger obj = (Passenger)it.next();
            print(obj.getName() + "-" + obj.getAge());
        }
    }

    public static void print(Object obj) {
        System.out.println(obj);
    }
}

class MyComparator implements Comparator {
    @Override
    public int compare(Object o1, Object o2) {
        if(!(o1 instanceof Passenger) || !(o2 instanceof Passenger)) {
            throw new RuntimeException("不可比较的对象");
        }
        Passenger p1 = (Passenger)o1;
        Passenger p2 = (Passenger)o2;
         System.out.println("调用compare比较"+ p1.getName() + "与" + p2.getName());
        if(p1.getAge() > p2.getAge()) {
            return 1;
        }
        if(p1.getAge() < p2.getAge()) {
            return -1;
        }
        return 0;
    }
}

运行结果:
-----------添加元素到TreeSet----------
调用compare比较zhangsan与zhangsan
调用compare比较lingsi与zhangsan
调用compare比较wangwu与zhangsan
调用compare比较wangwu与lingsi
调用compare比较chenliu与lingsi
调用compare比较chenliu与wangwu
zhangsan-20
lingsi-21
wangwu-22

View Code

从上面的例子可以看出,Passenger本身并不具备比较性,我们也没有修改Passenger,而是在外部自定义一个比较器,传入TreeSet中,使得TreeSet中存储的Passenger具有了比较性。

HashSet也不是线程安全的,可以在构造时添加同步操作。

 

 Set s = Collections.synchronizedSet(new HashSet;

通过**entrySet**遍历

葡京正网网投 26葡京正网网投 27

public class HashMapTest {

    public static void main(String[] args) {
        HashMap<String,String> map = new HashMap<String,String>();
        map.put("001", "zhangsan1");
        map.put("002", "zhangsan2");
        map.put("003", "zhangsan3");
        map.put("004", "zhangsan4");

        Set<Entry<String, String>> se = map.entrySet();
        Iterator<Entry<String, String>> it = se.iterator();
        while(it.hasNext()) {
            Entry<String, String> en = (Entry<String, String>)it.next();
            System.out.println(en.getKey() + "-" + en.getValue());
        }

    }
}

运行结果:
004-zhangsan4
001-zhangsan1
002-zhangsan2
003-zhangsan3

View Code

  • lowerEntry、floorEntry、ceilingEntry、higherEntry分别返回小于指定key、小于或等于指定key、大于或等于指定key和大于指定key的键值对(只返回最接近的一个键值对)。同理lowerKey、floorKey、ceilingKey、higherKey返回对应的键key。
  • 同时还提供了返回最小key、最大key的firstEntry、pollFirstEntry、lastEntry、pollLastEntry。
  • 最后NavigableMap还提供了倒序视图descendingMap、倒序键集合decendingKeySet和返回NavigableSet类型的键集合navigableKeySet()。

Set接口

Set是Collection的一个子接口,Set中的元素是无序的,不可以重复。定义如下:

public interface Set<E> extends Collection<E> {}

Set是继承于Collection接口,它自然就包含了Collection中的全部函数接口。Set接口的常用实现类有HashSet和TreeSet。实际上HashSet是通过HashMap实现的,TreeSet是通过TreeMap实现的。在此只简要列举它们的一些特点,可以直接看下面的HashMap和TreeMap的分析,理解了HashMap和TreeMap,也就理解了HashSet和TreeSet。

下面是AbstractMap具体方法实现:

HashMap举例

HashSet将元素作为HashMap的key进行存储,所有操作都是针对HashMap的key进行操作。

集合的作用与特点

Java是一门面向对象语言,数据多了用对象封装存储(比如,人有姓名、年龄、性别等数据信息,我们就抽象一个Person对象来封装存储),对象多了又用什么来存储呢?集合,集合就是用来存储对象的。

 

集合的特点就是适用于存储对象而且可以存储不同类型的对象,集合的长度是可变的。

 

接下来我们看看添加kv操作:

Collection接口

Collection是一个接口,是高度抽象出来的集合,包含了集合的基本操作:添加、删除、清空、遍历、是否为空、获取大小等等。定义如下:

public interface Collection<E> extends Iterable<E> {}

Collection接口下主要有两个子接口:List和Set。

葡京正网网投 28image.png

Collection集合

HashMap提供了四个构造方法:

[图片上传失败...(image-316f83-1548676054872)]

欢迎关注我的公众号,会定期推送优质技术文章,让我们一起进步、一起成长!公众号搜索:data_tc或直接扫码:

本文由葡京网投哪个正规发布于新葡亰-编程,转载请注明出处:葡京网投哪个正规源码解析,java集合框架总结

关键词:

上一篇:安卓常用第三方框架,GSON速学必会

下一篇:Gson基本操作,采用Gson解析含有多种JsonObject的复杂json