Java容器

 

 

 

 

红色代表接口，蓝色代表抽象类，绿色代表并发包中的类，灰色代表早期进程安全的类（基本上已过期）

 

arraylist

基于数组，支持快速随机访问

public class arraylist<e> extends abstractlist<e>
        implements list<e>, randomaccess, cloneable, java.io.serializable // 实现了randomaccess表示支持快速随机访问

数组默认大小为10，基于数组实现

private static final int default_capacity = 10;

transient object[] elementdata; // non-private to simplify nested class access

添加元素时会调用add（）方法，同时使用ensurecapacityinternal（）方法来保证调用add（）方法时数组的容量，当数组容量不够时，会调用grow（）方法进行扩容。

扩容代码：

private void grow(int mincapacity) {
        // overflow-conscious code
        int oldcapacity = elementdata.length;
        int newcapacity = oldcapacity + (oldcapacity >> 1); // 扩容大小为原来的1.5倍
　　　　　  ......
　　　　　　......
// mincapacity is usually close to size, so this is a win:
        elementdata = arrays.copyof(elementdata, newcapacity); // 将原来的数组拷贝进新的数组，扩容的代价高
    }

 

删除元素是会调用system.arraycopy()方法，将index+1后面的元素都复制到index的位置上，代价高

system.arraycopy(elementdata, index+1, elementdata, index, nummoved);

 

linkedlist

基于双向链表，在任意位置添加删除元素比arraylist快。

数据类型：

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;
        }
    }

 

hashmap

基于jdk1.7源码

 

 

entry内部类存储kv键值对

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;
    }
}

存储所有节点的数组：

transient entry[] table;

 

• hashmap使用拉链法将键值将kv数据打散分布在不同table[i]中。
• hashmap 通过 key 的 hashcode 经过hash()处理过后得到 hash 值，然后通过 hash & (length - 1)判断当前元素存放的位置（length为table[]的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就插入在链表头部。

 

hashmap添加元素，执行put（）操作，会先执行hash（）方法计算hash值，然后计算哈希桶的位置，hash值重复则覆盖，不重复则头插法插入链表，最后调用addentry（）方法添加键值对，如果键为null，默认插入table[0]上。

 

计算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);
}

public final int hashcode() {
    return objects.hashcode(key) ^ objects.hashcode(value);
}

 

计算哈希桶的位置

int hash = hash(key);
int i = indexfor(hash, table.length);

static int indexfor(int h, int length) {
    return h & (length-1);
}

 

hashmap扩容：

扩容使用resize（）方法，扩容大小为原来table[]数组的的两倍，然后调用transfer（）方法，将 oldtable 的所有键值对重新插入 newtable 中，扩容时会重新计算哈希桶的位置。

resize(2 * table.length);

 

concurrenthashmap

并发下使用的线程安全的 hashmap 的替代品。

 数据存储结构

static final class hashentry<k,v> {
    final int hash;
    final k key;
    volatile v value;
    volatile hashentry<k,v> next;
}

 

final segment<k,v>[] segments;

segment核心类继承自重入锁reentrantlock

static final class segment<k,v> extends reentrantlock implements serializable {

 

static final int default_concurrency_level = 16; // 默认并发级别为16

 concurrenthashmap 采用了分段锁（segment）技术，每个分段锁维护着几个桶（hashentry），多个线程可以同时访问不同分段锁上的桶。