Collection和Map的那些常用的类操作的实现原理简要理解笔记

时间：2022-09-20 19:47:44

内容更新中……

Java集合框架
集合类

  • Collection(interface)

    • List(interface)
      • ArrayList：数组实现，适合随机访问元素
      • LinkedList（实现了Queue接口）：链表实现，适合插入、删除、移动
      • Vector（与ArrayList相比多了个线程安全）

    • Set(interface)

      • HashSet（使用散列函数）——> 通过HashMap实现，add(E e)是通过HashMap的add(K,V)方法实现，E是K；remove(Object o)是通过HashMap的remove(Object o)实现的。按哈希值保存其值，通过Iterator迭代器访问hashset。
      • TreeSet（使用红黑树）——> 通过TreeMap实现。保存的值是排序的。
      • LinkedHashSet（链表结合散列函数）。继承了HashSet,通过LinkedHashMap实现的。值是按照插入的顺序存储的。（结构有HashMap，和LinkList。双向链表存储插入的Entry元素。）

    • Queue(interface)

  • Map(interface)

    • HashMap（可以存放null）
    • TreeMap（不可以存放null，排序功能）
    • HashTable（不可以存放null，与HashMap比多了个线程安全）

其中线程安全类除了上面说的Vector和HashTable外，还有Stack、Enumeration是线程安全类。
除此集合类外，线程安全的类还有StringBuffer等。

线程安全是指在访问方法时不允许别的线程去改变，并不是说一系列操作是同步的。
比如StringBuffer的apeend方法线程安全的，但是调用多次append方法可能会对最后的结果造成顺序上的差别（append单句是顺序的）。

几个类和接口的比较
Collection：接口，各种集合结构的父接口
Collections：专用静态类，包含各种有关集合操作的静态方法。提供一系列静态方法实现对各种集合的搜索、排序、线程安全化等操作。
Array：Java中最基本的一个存储结构，提供动态创建和访问Java数组的方法。元素类型必须相同。效率高，但容量固定无法改变。无法判断实际多少元素。
Arrays：静态类。专门用来操作数组，提供搜索、排序、复制等静态方法。

HashMap的设计：
数据结构中有数组和链表来存数据。
数组的优缺点：访问迅速，插入和删除难
链表的优缺点：插入和删除简单，访问复杂度高
这确实是两个极端。

如何综合数组和链表的特性，做出访问容易，插入和删除都容易的数据结构？
可以，就是哈希表（HashTable）：拉链法，使用数组，数组里面是链表（链表的数组，数组中存的是链表的头结点，就像邻接表一样）
这些元素是通过散列公式存进去的。

HashMap也是一个线性的数组实现的，其存储的容器就是一个线性数组。（如何用线性数组来存取键值对呢）
首先HashMap里面有一个静态内部类Entry，其重要的属性有key,value,next，从key，value看出来Entry是HashMap键值对实现的一个基础bean，HashMap的基础就是一个线性数组，这个数组就是Entry[]，Map里面的内容都保存在Entry[]里面。
transient Entry[] table;

HashMap的存取实现

//存储时
int hash = key.hashCode();
int index = hash % Entry[].length;
Entry[hash] = value;
//取值时
int hash = key.hashCode;
int index = hash % Entry[].length;
return Entry[index];

Put操作
如果两个key通过hash%Entry[].length得到的index相同会不会有覆盖的风险(两个不同的key拥有相同的index)。
因为有个next属性，作用是指向下一个Entry。如果A的index是0，B的index也是0，那么进来B的时候，A的next是B。index = 0的位置其实是放了三个键值对的。数组中存储的是最后插入的元素。

public V put(K key, V value){
if(k == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash,table.length);
//遍历链表，看有没有相同的，就是拉链法的那个拉链后面的东西
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)) )//如果key在链表中已存在，替换为新的value{
               V oldValue = e.value;
               e.value = value;
               e.recordAccess(this);
return oldValue;
          }
     }
     modCount++;
     addEntry(hash,key,value,i);
return null;
}

void addEntry(int hash ,K key , V value, int buketIndex)
{     
     Entry<K,V> e = table[buketIndex];
     table[bucketIndex] = new Entry<K,V>(hash,key,value,e);//e是Entry.next
if(size++ >= threshold)
          resize(2*table.length);
}

HashMap里面包含一些优化方面的实现，比如Entry数组的长度一定后，随着map里面数据的越来越长，这样同一个index的链长度就会很长，网HashMap里面设置一个引子，随着map的size越来越大，Entry[]会以一定的规则加长长度。

说完HashMap后，从源码来简单看看Collection的子接口List接口的实现类ArrayList的添加和删除元素到底是怎么操作的

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
return true;
    }

直接添加元素就是先判断是否需要扩容，然后直接把元素添加到末尾

    public void add(int index, E element) {
        rangeCheckForAdd(index);
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

先看这个添加的函数，在索引index处添加元素E element。
首先是确定index的范围，然后根据当前的size+1判断是否需要扩容（扩容机制：看当前的arraylist是否为空，如果为空就是取默认容量和传入参数的较大值，然后调用enSureExplicitCapacity方法进行扩容。
modCount++，然后看传入的size+1参数是否大于add之前数组 elementData 的大小，如果是，就调用grow方法进行扩容 newCapacity=oldCapacity+(oldCapacity>>1)，扩大1.5倍，然后将扩容后的数组复制一份Array.copyof给 elementData ）
再者就是使用native方法arraycopy去对数组进行一个复制。其声明如下：

public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
int length);

将elementData数组第index个元素后的元素拷到elementData从第index+1位置到后面的位置，长度是size-index。其实做的就是后移操作。

    public E remove(int index) {
        rangeCheck(index);
        modCount++;
        E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,numMoved);
        elementData[--size] = null; // clear to let GC do its work
return oldValue;
    }

至于这个移除第index个位置的元素操作，依旧先检查index的范围，修改次数modCount加1，然后获取要删除索引的元素的值。
然后就是数组往前移动覆盖到index的值，如果移动的长度要大于0，则使用System.arraycopy 的方法去复制数组；然后把数组的最后一个元素置空，让GC去回收它，返回的是一个旧的元素的值。

（PS：在一个迭代器初始的时候会赋予它调用这个迭代器的对象的mCount，如何在迭代器遍历的过程中，一旦发现这个对象的mcount和迭代器中存储的mcount不一样那就抛异常。
下面是这个mcount相关机制的解释引用：
Fail-Fast 机制
我们知道 java.util.HashMap 不是线程安全的，因此如果在使用迭代器的过程中有其他线程修改了map，那么将抛出ConcurrentModificationException，这就是所谓fail-fast策略。这一策略在源码中的实现是通过 modCount 域，modCount 顾名思义就是修改次数，对HashMap 内容的修改都将增加这个值，那么在迭代器初始化过程中会将这个值赋给迭代器的 expectedModCount。在迭代过程中，判断 modCount 跟 expectedModCount 是否相等，如果不相等就表示已经有其他线程修改了 Map：注意到 modCount 声明为 volatile，保证线程之间修改的可见性。所以当大家遍历那些非线程安全的数据结构时，尽量使用迭代器）

由此也可以联想在遍历ArrayList的过程中，不能add和remove元素，此时会报错误
java.util.ConcurrentModificationException

    public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
                    fastRemove(index);
return true;
                }
        } else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
                    fastRemove(index);
return true;
                }
        }
return false;
    }

再看一下这个移除object的操作，如果要移除的对象为空，List是可以添加null的。所以需要遍历list，然后根据index去查看如果有相同的那么就用新的数组去覆盖原来旧的数组。

    private void fastRemove(int index) {
        modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,numMoved);
        elementData[--size] = null; // clear to let GC do its work
    }

移除元素操作用到了快速移除fastRemove方法，与remove(int index)方法类似，只是不需要检查index的范围，因为这个index已经确定好是存在的。

    public void clear() {
        modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
            elementData[i] = null;
        size = 0;
    }

clear元素很简单，全部置空然后长度归0

    public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
return numNew != 0;
    }

往ArrayList中添加实现Collection的类，先转换成Object数组，然后判断当前默认值和传入参数（两个list的长度和）确定是否需要扩容，再把新的数组a复制到数组的末尾。

    public boolean addAll(int index, Collection<? extends E> c) {
        rangeCheckForAdd(index);
        Object[] a = c.toArray(); // c可以转换成数组
int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,numMoved);
        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
return numNew != 0;
    }

在指定位置index中往ArrayList中添加实现Collection的类，先转换成Object数组，然后判断当前默认值和传入参数（两个list的长度和）确定是否需要扩容，把原list数组index及以后的数据移到index+numNew（要添加数组的长度）处，再把新的数组a复制到数组的index处，再更新新list的size。

public boolean removeAll(Collection<?> c) {
        Objects.requireNonNull(c);
return batchRemove(c, false);
    }

removeAll首先需要判断要移除的c是否为空，如果为空，抛出空指针异常。

removeAll基于batchRemove来实现的，batchRemove源码如下：

private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
                    elementData[w++] = elementData[r];
        } finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
if (r != size) {
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                w += size - r;
            }
if (w != size) {
// clear to let GC do its work
for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;
                size = w;
                modified = true;
            }
        }
return modified;
    }

先将当前的数据备份到同步局部变量final数组elementData（这个数组不能指向其它数组对象，内容可以变），设置读写两个指针r,w。遍历当前list，把当前list中除了要移除的元素之外的元素保存到elementData中。如果没能遍历完list（可能c.contains抛出异常），将未能够遍历的元素（index为r之后）全部复制到w指位置后（类似于未能遍历元素的恢复）。w指针更新位置（w位置和w之前的元素就是新数组的元素）。如果w位置不在list末尾，说明元素改动过了（至少有一次c.contains为true），此时将w后面多余的元素删除置空，让GC回收它们。

标签：

相关文章