欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Java容器

程序员文章站 2022-05-15 13:23:10
红色代表接口,蓝色代表抽象类,绿色代表并发包中的类,灰色代表早期进程安全的类(基本上已过期) ArrayList 基于数组,支持快速随机访问 数组默认大小为10,基于数组实现 添加元素时会调用add()方法,同时使用ensureCapacityInternal()方法来保证调用add()方法时数组的 ......

 

 

 

 

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源码

Java容器

 

Java容器

 

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扩容:

Java容器

扩容使用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),多个线程可以同时访问不同分段锁上的桶。