java集合实现方式
java集合实现方式
追逐技术的IT人 发表于8个月前
java集合实现方式
  • 发表于 8个月前
  • 阅读 13
  • 收藏 0
  • 点赞 0
  • 评论 0

标题:腾讯云 新注册用户域名抢购1元起>>>   

1.ArrayList

底层通过数组实现。除该类未实现同步外,不是线程安全的,其余跟Vector大致相同,Vector是线程安全的。

set()方法非常简单,直接对数组的指定位置赋值即可

public E set(int index, E element) {
    rangeCheck(index);//下标越界检查
    E oldValue = elementData(index);
    elementData[index] = element;//赋值到指定位置,复制的仅仅是引用
    return oldValue;
}

get()方法同样很简单,唯一要注意的是由于底层数组是Object[],得到元素后需要进行类型转换。

public E get(int index) {
    rangeCheck(index);
    return (E) elementData[index];//注意类型转换
}

add(E e)与add(int index, E e)这两个方法都是向容器中添加新元素,这可能会导致capacity不足,因此在添加元素之前,都需要进行剩余空间检查,如果需要则自动扩容。扩容操作最终是通过grow()方法完成的,添加的仅仅是引用。

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);//原来的1.5倍
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);//扩展空间并复制
}

remove()方法有两个版本,一个是remove(int index)删除指定位置的元素,另一个是remove(Object o)删除第一个满足o.equals(elementData[index])的元素。删除操作是add()操作的逆过程,需要将删除点之后的元素向前移动一个位置。需要注意的是为了让GC起作用,必须显式的为最后一个位置赋null值。

public E remove(int index) {
    rangeCheck(index);//检查index的合法性
    modCount++;//修改版本加1
    E oldValue = elementData(index);
    int numMoved = size - index - 1;//要移动的元素个数
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    elementData[--size] = null; //清除该位置的引用,让GC起作用
    return oldValue;
}

关于Java GC这里需要特别说明一下,有了垃圾收集器并不意味着一定不会有内存泄漏。对象能否被GC的依据是是否还有引用指向它,上面代码中如果不手动赋null值,除非对应的位置被其他元素覆盖,否则原来的对象就一直不会被回收。

2.LinkedList

底层通过双向链表实现,双向链表的每个节点用内部类Node表示。LinkedList通过first和last引用分别指向链表的第一个和最后一个元素。当链表为空的时候first和last都指向null。LinkedList的实现方式决定了所有跟下标相关的操作都是线性时间,而在首段或者末尾删除元素只需要常数时间。为追求效率LinkedList没有实现同步(synchronized),如果需要多个线程并发访问,可以先采用Collections.synchronizedList()方法对其进行包装。

Node内部类
private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

add(E e)
public boolean add(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;//原来链表为空,这是插入的第一个元素
    else
        l.next = newNode;
    size++;
    return true;
}

add(int index, E element)的逻辑稍显复杂,可以分成两部,1.先根据index找到要插入的位置;2.修改引用,完成插入操作。

public void add(int index, E element) {
    checkPositionIndex(index);//index >= 0 && index <= size;
    if (index == size)//插入位置是末尾,包括列表为空的情况
        add(element);
    else{
        Node<E> succ = node(index);//1.先根据index找到要插入的位置
        //2.修改引用,完成插入操作。
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)//插入位置为0
            first = newNode;
        else
            pred.next = newNode;
        size++;
    }
}

上面代码中的node(int index)函数有一点小小的trick,因为链表双向的,可以从开始往后找,也可以从结尾往前找,具体朝那个方向找取决于条件index < (size >> 1),也即是index是靠近前端还是后端。

remove方法:两个删除操作都要1.先找到要删除元素的引用,2.修改相关引用,完成删除操作。在寻找被删元素引用的时候remove(Object o)调用的是元素的equals方法,而remove(int index)使用的是下标计数,两种方式都是线性时间复杂度。在步骤2中,两个revome()方法都是通过unlink(Node<E> x)方法完成的。这里需要考虑删除元素是第一个或者最后一个时的边界情况。

unlink(Node<E> x),删除一个Node
E unlink(Node<E> x) {
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;
    if (prev == null) {//删除的是第一个元素
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }
    if (next == null) {//删除的是最后一个元素
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }
    x.item = null;//let GC work
    size--;
    return element;
}

get(int index)方法得到指定下标处元素的引用,通过调用上文中提到的node(int index)方法实现。

public E get(int index) {
    checkElementIndex(index);//index >= 0 && index < size;
    return node(index).item;
}

set(int index, E element)方法将指定下标处的元素修改成指定值,也是先通过node(int index)找到对应下表元素的引用,然后修改Node中item的值。

public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;//替换新值
    return oldVal;
}

3.ArrayDeque

    双端队列,它既可以当作栈使用,也可以当作队列使用。 ArrayDeque底层通过数组实现,为了满足可以同时在数组两端插入或删除元素的需求,该数组还必须是循环的,即循环数组(circular array),也就是说数组的任何一点都可能被看作起点或者终点。ArrayDeque是非线程安全的(not thread-safe),当多个线程同时使用的时候,需要程序员手动同步;另外,该容器不允许放入null元素。head指向首端第一个有效元素,tail指向尾端第一个可以插入元素的空位。因为是循环数组,所以head不一定总等于0,tail也不一定总是比head大。

addFirst(E e)的作用是在Deque的首端插入元素,也就是在head的前面插入元素,在空间足够且下标没有越界的情况下,只需要将elements[--head] = e即可。 实际需要考虑:1.空间是否够用,以及2.下标是否越界的问题。

public void addFirst(E e) {
    if (e == null)//不允许放入null
        throw new NullPointerException();
    elements[head = (head - 1) & (elements.length - 1)] = e;//2.下标是否越界
    if (head == tail)//1.空间是否够用
        doubleCapacity();//扩容
}

空间问题是在插入之后解决的,因为tail总是指向下一个可插入的空位,也就意味着elements数组至少有一个空位,所以插入元素的时候不用考虑空间问题。下标越界的处理解决起来非常简单,head = (head - 1) & (elements.length - 1)就可以了,这段代码相当于取余,同时解决了head为负值的情况。因为elements.length必需是2的指数倍,elements - 1就是二进制低位全1,跟head - 1相与之后就起到了取模的作用,如果head - 1为负数(其实只可能是-1),则相当于取elements.length -1的值。

doubleCapacity(),其逻辑是申请一个更大的数组(原数组的两倍),然后将原数组复制过去。

private void doubleCapacity() {
    assert head == tail;
    int p = head;
    int n = elements.length;
    int r = n - p; // head右边元素的个数
    int newCapacity = n << 1;//原空间的2倍
    if (newCapacity < 0)
        throw new IllegalStateException("Sorry, deque too big");
    Object[] a = new Object[newCapacity];
    System.arraycopy(elements, p, a, 0, r);//复制右半部分,对应上图中绿色部分
    System.arraycopy(elements, 0, a, r, p);//复制左半部分,对应上图中灰色部分
    elements = (E[])a;
    head = 0;
    tail = n;
}

addLast(E e)的作用是在Deque的尾端插入元素,也就是在tail的位置插入元素,由于tail总是指向下一个可以插入的空位,因此只需要elements[tail] = e;即可。插入完成后再检查空间,如果空间已经用光,则调用doubleCapacity()进行扩容。

public void addLast(E e) {
    if (e == null)//不允许放入null
        throw new NullPointerException();
    elements[tail] = e;//赋值
    if ( (tail = (tail + 1) & (elements.length - 1)) == head)//下标越界处理
        doubleCapacity();//扩容
}

pollFirst()的作用是删除并返回Deque首端元素,也即是head位置处的元素。如果容器不空,只需要直接返回elements[head]即可,当然还需要处理下标的问题。由于ArrayDeque中不允许放入null,当elements[head] == null时,意味着容器为空。

public E pollFirst() {
    E result = elements[head];
    if (result == null)//null值意味着deque为空
        return null;
    elements[h] = null;//let GC work
    head = (head + 1) & (elements.length - 1);//下标越界处理
    return result;
}

pollLast()的作用是删除并返回Deque尾端元素,也即是tail位置前面的那个元素。

public E pollLast() {
    int t = (tail - 1) & (elements.length - 1);//tail的上一个位置是最后一个元素
    E result = elements[t];
    if (result == null)//null值意味着deque为空
        return null;
    elements[t] = null;//let GC work
    tail = t;
    return result;
}

peekFirst()的作用是返回但不删除Deque首端元素,也即是head位置处的元素,直接返回elements[head]即可。

public E peekFirst() {
    return elements[head]; // elements[head] is null if deque empty
}

peekLast()的作用是返回但不删除Deque尾端元素,也即是tail位置前面的那个元素。

public E peekLast() {
    return elements[(tail - 1) & (elements.length - 1)];
}

下面列出了ArrayDeque与队列相对应的接口:

addLast(e)向队尾插入元素,失败则抛出异常
offerLast(e)向队尾插入元素,失败则返回false
removeFirst()获取并删除队首元素,失败则抛出异常
pollFirst()获取并删除队首元素,失败则返回null
getFirst()获取但不删除队首元素,失败则抛出异常
peekFirst()获取但不删除队首元素,失败则返回null

下面列出了ArrayDeque与堆栈相对应的接口:

addFirst(e)向栈顶插入元素,失败则抛出异常
offerFirst(e)向栈顶插入元素,失败则返回false
removeFirst()获取并删除栈顶元素,失败则抛出异常
pollFirst()获取并删除栈顶元素,失败则返回null
peekFirst()获取但不删除栈顶元素,失败则抛出异常
peekFirst()获取但不删除栈顶元素,失败则返回null

4.HashSet和HashMap:二者在Java里有着相同的实现,前者仅仅是对后者做了一层包装,也就是说HashSet里面有一个HashMap(适配器模式)。HashMap采用Entry<K,V> table[]实现,table中的每一项都是Entry<K,V>的链表,存储了hash值一样的链表,也就是通过冲突链表方式解决问题。将对向放入到HashMap或HashSet中时,有两个方法需要特别关心:hashCode()和equals()。hashCode()方法决定了对象会被放到哪个bucket里,当多个对象的哈希值冲突时,equals()方法决定了这些对象是否是“同一个对象”。所以,如果要将自定义的对象放入到HashMap或HashSet中,需要@Override hashCode()和equals()方法。出于性能原因,HashMap是非同步的(not synchronized),如果需要在多线程环境使用,需要程序员手动同步;或者通过如下方式将HashMap包装成(wrapped)同步的:Map m = Collections.synchronizedMap(new HashMap(...));

get(Object key)方法根据指定的key值返回对应的value,该方法调用了getEntry(Object key)得到相应的entry,然后返回entry.getValue()。因此getEntry()是算法的核心。
算法思想是首先通过hash()函数得到对应bucket的下标,然后依次遍历冲突链表,通过key.equals(k)方法来判断是否是要找的那个entry。

final Entry<K,V> getEntry(Object key) {
    ......
    int hash = (key == null) ? 0 : hash(key);
    for (Entry<K,V> e = table[hash&(table.length-1)];//得到冲突链表
         e != null; e = e.next) {//依次遍历冲突链表中的每个entry
        Object k;
        //依据equals()方法判断是否相等
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    }
    return null;
}

上述代码中的hash(k)&(table.length-1)等价于hash(k)%table.length,原因是HashMap要求table.length必须是2的指数,因此table.length-1就是二进制低位全是1,跟hash(k)相与会将哈希值的高位全抹掉,剩下的就是余数了。

put(K key, V value)方法是将指定的key, value对添加到map里。该方法首先会对map做一次查找,看是否包含该元组,如果已经包含则直接返回,查找过程类似于getEntry()方法;如果没有找到,则会通过addEntry(int hash, K key, V value, int bucketIndex)方法插入新的entry,插入方式为头插法。

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 = hash & (table.length-1);//hash%table.length
    }
    //在冲突链表头部插入新的entry
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

remove(Object key)的作用是删除key值对应的entry,该方法的具体逻辑是在removeEntryForKey(Object key)里实现的。removeEntryForKey()方法会首先找到key值对应的entry,然后删除该entry(修改链表的相应指针)。查找过程跟getEntry()过程类似。

final Entry<K,V> removeEntryForKey(Object key) {
    ......
    int hash = (key == null) ? 0 : hash(key);
    int i = indexFor(hash, table.length);//hash&(table.length-1)
    Entry<K,V> prev = table[i];//得到冲突链表
    Entry<K,V> e = prev;
    while (e != null) {//遍历冲突链表
        Entry<K,V> next = e.next;
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k)))) {//找到要删除的entry
            modCount++; size--;
            if (prev == e) table[i] = next;//删除的是冲突链表的第一个entry
            else prev.next = next;
            return e;
        }
        prev = e; e = next;
    }
    return e;
}

HashSet是对HashMap的简单包装,对HashSet的函数调用都会转换成合适的HashMap方法。

public class HashSet<E>
{
    ......
    private transient HashMap<E,Object> map;//HashSet里面有一个HashMap
    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();
    public HashSet() {
        map = new HashMap<>();
    }
    ......
    public boolean add(E e) {//简单的方法转换
        return map.put(e, PRESENT)==null;
    }
    ......
}

 

 

标签: Java
共有 人打赏支持
粉丝 4
博文 23
码字总数 33703
×
追逐技术的IT人
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: