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),多个线程可以同时访问不同分段锁上的桶。
上一篇: 姜茶是啥及制作方法