1.9 各种集合底层实现
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
header = new Entry(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 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 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 p = getEntry(key); return (p==null ? null : p.value); } put 方法的部分代码块: 根据比较大小决定是放在某个结点的左边还 是右边,如果值相同直接覆盖。左边大右边小 if (cpr != null) { do { parent = t; cmp = cprpare(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(); } public boolean add(E e) { return map.put(e, PRESENT)==null; }
TreeSet:TreeMap
public TreeSet() { this(new TreeMap()); } public boolean add(E e) { return m.put(e, PRESENT)==null; }