很長時間以來一直代碼中用的比較多的數據列表主要是List，而且都是ArrayList，感覺有這個玩意就夠了。ArrayList是用於實現動態數組的包裝工具類，這樣寫代碼的時候就可以拉進拉出，迭代遍歷，蠻方便的。 也不知道從什麼時候開始慢慢的代碼中就經常會出現HashMap和HashSet之類的工具類 ...
很長時間以來一直代碼中用的比較多的數據列表主要是List，而且都是ArrayList，感覺有這個玩意就夠了。ArrayList是用於實現動態數組的包裝工具類，這樣寫代碼的時候就可以拉進拉出，迭代遍歷，蠻方便的。 也不知道從什麼時候開始慢慢的代碼中就經常會出現HashMap和HashSet之類的工具類。應該說HashMap比較多一些，而且還是面試經典題，平時也會多看看。開始用的時候簡單理解就是個鍵值對應表，使用鍵來找數據比較方便。隨後深入瞭解後發現這玩意還有點小奧秘，特別是新版本的JDK對HashMap的改成樹後，代碼都有點小複雜咯。 Set開始用的較少，只是無意中在一個代碼中發現一個TreeSet，發現這個類可以自帶順利，感覺蠻有點意思，才慢慢的發現這也是個好工具啊。 代碼寫的多了就感覺到基礎的重要性，所以在此寫一篇小文簡單的整理一下對集合的一些知識。 好了，簡單的整理一下：
- List：即是列表，支持數組、鏈表的功能，一般都是線性的
- Map：即是映射表，存儲的是鍵與值的對應關係
- Set：即是集合的意思，主要是用於排重數據及排序
先來看看List
List是用於存放線性數據的一種視窗，比如：用於數組的ArrayList和用於鏈表的LinkedList。ArrayList
這是一個數組列表，不過提供了自動擴容的功能，實現List介面，外部操作都是通過介面申明的方法訪問，這樣即安全又方便。 ArrayList的關鍵就是自動擴容，在對象初始化時可以設定初始容量，也可以按預設的容量。如果對數組大小沒有特別明確可以不指定初始大小，如果明確的話可以指定一個大小，這樣減少動態擴容時產生的卡頓。說到這就要說一下擴容是怎麼實現的了，看下麵的代碼：| 1 2 3 4 5 6 7 8 9 10 11 |
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
|
LinkedList
這是針對鏈表的工具類，鏈表的優秀是添加刪除啥的比較快，但是查找會慢一些。 至於代碼好像也沒什麼特別的，就是一串指針鏈接起來，當然Java中就使用對象來代替，建立一個Node的對象，Node本身指向了前一個Node和後一個Node，這就是鏈表的結構：| 1 2 3 4 5 6 7 8 9 10 11 |
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;
}
}
|
| 1 2 3 4 5 6 7 8 9 10 11 12 13 |
/**
* Pointer to first node.
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;
/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;
|
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
/**
* Links e as last element.
*/
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
|
再來看看Map
Map是鍵與值做一個映射表的應用，主要的實現類：HashMap,HashTable,TreeMapHashMap和HashTable
使用hash演算法進行鍵值映射的就是HashMap啦，HashTable是帶有同步的線程安全的類，它們兩主要的區別就是這個。原理也類似，都是通過桶+鏈來組合實現。桶是用來存Key的，而由於Hash碰撞的原因值需要用一個鏈表來存儲。- 桶的意義在於高效，通過Hash計算可以一步定位
- 鏈表的意義在於存取重覆hash的數據
TreeMap
看過TreeMap的代碼後發現還是使用的樹結構，紅黑樹。由於紅黑樹是有序的，所以自然帶排序功能。當然也可通過comparator來指定比較方法來實現特定的排序。 因為採用了樹結構存儲那麼添加和刪除數據時會麻煩一些，看一下put的代碼：| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) {
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
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);
}
else {
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
|
最後看看Set
Set主要是兩類應用：HashSet和TreeSet。HashSet
字面意思很明確，使用了Hash的集合。這種集合的特點就是使用Hash演算法存數據，所以數據不重覆，存取都相對較快。怎麼做到的呢？| 1 2 3 4 |
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
|
| 1 |
private transient HashMap<E,Object> map;
|
TreeSet
這個集合是用於對集合進行排序的，也就是除了帶有排重的能力外，還可以自帶排序功能。只不過看了TreeSet的代碼發現，其就是在TreeMap的基礎實現的。更準確的說應該是NavigableMap的派生類。預設不指定map情況下TreeSet是以TreeMap為基礎的。| 1 2 3 |
public TreeSet() {
this(new TreeMap<E,Object>());
}
|
| 1 2 3 |
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
|
