各种集合底层实现
ArrayList: object[]
代码片段:构造方式
public ArrayList() {
this(10);//默认一开始构造了size为10的Object数组
}
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
this.elementData = new Object[initialCapacity];
}
优缺点:读快改慢
linkedList: Entry链表 ,单向链表
private transient Entry<E> header = new Entry<E>(null, null, null);
public LinkedList() {
header.next = header.previous = header;
}
优缺点:读慢改快
HashMap:Entry[]
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY];//构建Entry数组
init();
}
public V get(Object key) { //获取的时候从数组中读取
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}
//put方法 put的时候需要首先遍历数组的,看是否有重复的key
public V put(K key, V value) {
if (key == 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))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
TreeMap: 基于Entry的二叉树
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}
put方法的部分代码块:根据比较大小决定是放在某个结点的左边还是右边,如果值相同直接覆盖。左边大右边小
if (cpr != null) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
HashSet: 基于HashMap实现,因为map中的key是不能重复的
public HashSet() {
map = new HashMap<E,Object>();
}
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
TreeSet:TreeMap
public TreeSet() {
this(new TreeMap<E,Object>());
}
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
|