Java—Collection、Map、树
Collection? <類型>
? ? List?可以重復，有順序? ?可存放多個null值
? ? ? ? ? ? ArrayList??? ?主選?
? ? ? ? ? ? 結構：數組? ? ? 特點：查找快，增刪慢? ? ? ? ?線程不安全，效率高
? ? ? ? ? ? Vector
? ? ? ? ? ? 結構：數組? ? ? 特點：查找快，增刪慢? ? ? ? ? synchronized實現線程安全，效率低
? ? ? ? ? ? Stack?
? ? ? ? ? ? 結構：棧? ? ? ? ? 特點：Vector的子類，也定義了自己的一些方法。? ? ? ?synchronized實現線程安全，效率低
? ? ? ? ? ? LinkedList
? ? ? ? ? ? 結構：鏈表? ? ? 特點：查找慢，增刪快? ? ? ? ? 線程不安全，效率低
boolean add(E o) 向列表的尾部追加指定的元素void add(int index,E element) 在列表的指定位置插入指定元素。boolean addAll(Collection<? extends E> c) 追加指定 collection中的所有元素到此列表的結尾，順序是指定collection的迭代器返回這些元素的順序。boolean addAll(int index,Collection<? extends E> c) 將指定collection中的所有元素都插入到列表中的指定位置。void clear() 從列表中移除所有元素。boolean contains(Object o) 如果列表包含指定的元素，則返回true。boolean containsAll(Collection<?> c) 如果列表包含指定collection的所有元素，則返回true。boolean equals(Object c) 比較指定的對象與列表是否相等。E get(int index) 返回列表中指定位置的元素。int hashCode() 返回列表的哈希碼值。int indexOf(Object o) 返回列表中首次出現指定元素的索引，如果列表不包含此元素，則返回-1。boolean isEmpty() 判斷集合是否為空 如果為空 則返回true,否則返回falseIterator<E> iterator() 返回以正確順序在列表的元素上進行迭代的迭代器。int lastIndexOf(Object o) 返回列表中最后出現指定元素的索引，如果列表不包含此元素，則返回-1。ListIterator<E> listIterator() 返回列表中元素的列表迭代器（以正確的順序）。ListIterator<E> listIterator(int index)返回列表中元素的列表迭代器（以正確的順序），從列表的指定位置開始。E remove(int index) 移除列表中指定位置的元素。boolean remove(Object o) 移除列表中出現的首個指定元素。boolean removeAll(Collection<?> c) 從列表中移除指定collection中包含的所有元素。boolean retainAll(Collection<?> c)僅在列表中保留指定collection中所包含的元素。E set(int index,E element) 用指定元素替換列表中指定位置的元素。int size() 返回列表中的元素數。List<E> subList(int forIndex,int toIndex) 返回列表中指定的formIndex(包括) 和toIndex(不包括)之間的部分視圖。Object toArray() 返回以正確順序包含列表中的所有元素的數組。? ? Set? 唯一性，沒有順序? ?只可存放一個null值
? ? ? ? ? ? HashSet?
? ? ? ? ? ? 結構：哈希表? ? ?通過hashCode()、equals()保證元素的唯一性? ? ?元素的排列是無序的? ?線程不安全
? ? ? ? ? ? 基于 HashMap 實現的，HashSet 底層使用 HashMap 來保存所有元素
? ? ? ? ? ? LinkedHashSet
? ? ? ? ? ? 結構：鏈表+哈希表? ?與HashSet相比，由鏈表保證元素有序? ?線程不安全
? ? ? ? ? ? TreeSet
? ? ? ? ? ? 結構：紅黑樹? ? ?排序方法有自然排序、比較器排序? ? 唯一性通過存放值時比較返回值是否為0，0既有相同值? ?線程不安全
? ? ? ? ? ? TreeSet實現了對TreeMap的封裝
? ? ? ? ? ? 實現了Serializable接口，因此它支持序列化，實現了Cloneable接口，能被克隆
Hash值沖突
? ? hash值沖突是發生在put()時，hash值是通過hash(key.hashCode())來獲取的，因為hashCode是int類型，所以最多只能說2^32個，當put的元素越來越多時，出現不同的key產生相同的hash值問題，也即是hash沖突。
分離鏈表法
? ? 對于相同的哈希值，使用鏈表進行連接。使用數組存儲每一個鏈表。
? ? put的時候地址上存在value，則再對比key是否相同,若hash值和key都相同，則替換value，若hash值相同，key不相同，則形成一個單鏈表，將hash值相同，key不同的元素以Entry<V,V>的方式存放在鏈表中，這樣就解決了hash沖突。
開放地址方法
? ? ? ? ? ? 按順序決定哈希值時，如果某數據的哈希值已經存在，則在原來哈希值的基礎上往后加一個單位，直至不發生哈希沖突。
equals 和 hashCode區別：
- 在Object類中，hashCode是一個本地方法簡單理解為獲取對象地址，equals方法比較自己和obj對象地址是否相 等。在這里一定先認識到這兩個方法，一個是取地址，一個是比較地址。equals()和hashCode()都不是final方法。
- hashCode()是一個native方法，而且返回值類型是整形；該native方法將對象在內存中的地址作為哈希碼返回，可以保證不超出整形范圍的情況下不同對象的返回值不同。
- 當我們向哈希表(如HashSet、HashMap等)中添加對象object時，首先調用hashCode()方法計算object的哈希碼，通過哈希碼可以直接定位object在哈希表中的位置(一般是哈希碼對哈希表大小取余)。如果該位置沒有對象，可以直接將object插入該位置；如果該位置有對象(可能有多個，通過鏈表實現)，則調用equals()方法比較這些對象與object是否相等，如果相等，則不需要保存object；如果不相等，則將該對象加入到鏈表中。
注：當我們把自定義類作為Map的Key的時候，需要重寫HashCode跟equals方法，原因是要遵循equals相等，hashCode也一定相等，hashCode相等，equals不一定相等的規則。String就重寫的這兩個方法。
Map<key,value>
? ? HashMap? ? 主選
? ? ? ? ? ? 結構：哈希表（數組+鏈表）? 無序的 只允許一個key為null，可多個值為null? ??線程不安全
? ? ? ? ? ? 采用分離鏈表法解決沖突
? ? ? ? ? ? 通過hashCode()、equals()保證元素的唯一性，hashCode()確定數組位置，equlas()確定是否可存放在鏈表。
? ? ? ? ? ? 實現了Serializable接口，因此它支持序列化，實現了Cloneable接口，能被克隆。
? ? ? ? ? ??JDK1.8增加了紅黑樹來進行優化。即當鏈表超過8時，鏈表就轉換為紅黑樹，利用紅黑樹快速增刪改查的特點提高HashMap的性能。
? ? ? ? ? ? 缺點：多線程put會陷入死循環，因為Entry鏈表形成環形數據結構，查找時會陷入死循環。用迭代器遍歷時修改集合結構會發生錯誤。
? ? ? ? ? ? 遍歷方法：
Map<Integer, Integer> map = new HashMap<Integer, Integer>();Iterator<Map.Entry<Integer, Integer>> entries = map.entrySet().iterator();while (entries.hasNext()) {Map.Entry<Integer, Integer> entry = entries.next();System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue());}? ?LinkedHashMap??
? ? ? ? ? ? 結構：數組+雙鏈表
? ? ? ? ? ? 與HashMap相比，LinkedHashMap 的元素是有序的，在LruCache中有使用，因為是LRU，最近最少使用算法需要支持有序。
? ?HashTable
? ? ? ? ? ? 結構：哈希表? ? ?key還是value都不能為null? ?synchronized實現線程安全
? ? ? ? ? ? 實現了Serializable接口，它支持序列化，實現了Cloneable接口，能被克隆
? ?TreeMap
? ? ? ? ? ? 結構：紅黑樹? ? ??排序方法有自然排序、比較器排序? ? ? 線程不安全? 可以插入null鍵，null值；
? ? ? ? ? ??無序集合（插入和遍歷順序不一致）
常用方法：
void clear() 從此映射中移除所有映射關系（可選操作）。boolean containsKey(Object key) 如果此映射包含指定鍵的映射關系，則返回 true。boolean containsValue(Object value) 如果此映射將一個或多個鍵映射到指定值，則返回 true。Set<Map.Entry<K,V>> entrySet() 返回此映射中包含的映射關系的 Set 視圖。boolean equals(Object o) 比較指定的對象與此映射是否相等。V get(Object key) 返回指定鍵所映射的值；如果此映射不包含該鍵的映射關系，則返回 null。int hashCode() 返回此映射的哈希碼值。boolean isEmpty() 如果此映射未包含鍵-值映射關系，則返回 true。Set<K> keySet() 返回此映射中包含的鍵的 Set 視圖。V put(K key, V value) 將指定的值與此映射中的指定鍵關聯（可選操作）。void putAll(Map<? extends K,? extends V> m) 從指定映射中將所有映射關系復制到此映射中（可選操作）。V remove(Object key) 如果存在一個鍵的映射關系，則將其從此映射中移除（可選操作）。int size() 返回此映射中的鍵-值映射關系數。Collection<V> values() 返回此映射中包含的值的 Collection 視圖。Queue? FIFO隊列
操作失敗就拋出異常add(E e)：添加一個元素到隊尾remove()：獲取隊首的元素，并從隊列中移除element()：獲取隊首的元素，但不從隊列中移除這一組，成功返回true，失敗時返回一個特殊值(取決于操作，為NULL或false)，offer(E e)操作是專為容量受限的隊列實現而設計的；在大多數實現中，插入操作不會失敗。offer(E e)：添加一個元素到隊尾poll()：獲取隊首的元素，并從隊列中移除peek()：獲取隊首的元素，但不從隊列中移除迭代器（Iterator）
迭代器是一種設計模式，它是一個對象，它可以遍歷并選擇序列中的對象，而開發人員不需要了解該序列的底層結構。迭代器通常被稱為“輕量級”對象，因為創建它的代價小。
Java中的Iterator功能比較簡單，并且只能單向移動：
- ?使用方法iterator()要求容器返回一個Iterator。第一次調用Iterator的next()方法時，它返回序列的第一個元素。注意：iterator()方法是java.lang.Iterable接口,被Collection繼承。
- hasNext():判斷當前元素是否存在，并沒有指向的移動
- next():返回當前元素， 并指向下一個元素
- 使用remove()將迭代器新返回的元素刪除。
Iterator是Java迭代器最簡單的實現，為List設計的ListIterator具有更多的功能，它可以從兩個方向遍歷List，也可以從List中插入和刪除元素。
樹：
滿二叉樹：除了葉節點外每一個結點都有左右子女且葉節點都處在最底層的二叉樹。
?
完全二叉樹：只有最下面的兩層結點度小于2，并且最下面一層的結點都集中在該層最左邊的若干位置的二叉樹。
?
二叉樹：查找最好O(logN)，最差O(N)，最差情況是所有的數據全部在一端時。
反轉二叉樹
if(root==null) return; else reverseTree(root); public void reverseTree(Node node){if(node.left!=null) reverseTree(node.left);if(node.right!=null) reverseTree(node.right);Node temp = node.right;node.right = node.left;node.left = temp; }二叉查找樹：查找最好O(logN)，最差O(N)，最差情況是所有的數據全部在一端時
1.若任意結點的左子樹不空，則左子樹上所有結點的值均不大于它的根結點的值。
2. 若任意結點的右子樹不空，則右子樹上所有結點的值均不小于它的根結點的值。
3.任意結點的左、右子樹也分別為二叉搜索樹。
public class Node {public int index;//關鍵字段public String data;//值public Node leftNode;//左節點public Node rightNode;//右節點 }//查找 public Node findNode(int key){Node current = root;while(current.index != key){if(key < current.index){//左節點current = current.leftNode;}else{//右節點current = current.rightNode;}if(current == null){return null;}}return current; }//插入 public void insertNode(int key,String value){Node node = new Node();node.index = key;node.data = value;if(root == null){root = node;return;}//找到插入節點的位置Node parent = root;Node current = root;while(true){parent = current;if(key == current.index){return;}if(key < current.index){//左節點current = current.leftNode;if(current == null){//當前節點已經是葉子結點了parent.leftNode = node; return;}}else{current = current.rightNode;if(current == null){parent.rightNode = node;return;}}} }平衡二叉樹：又稱為AVL樹，查找O(logN)，它是一顆空樹或它的左右兩個子樹的高度差的絕對值不超過1
哈夫曼樹：帶權路徑長度達到最小的二叉樹，也叫做最優二叉樹。
k層的二叉樹，最多有節點個數為 2^k-1，最少有k個節點
第k層，最多有節點個數為 2^(k-1)個
紅黑樹：查找刪除插入時間復雜度O(logN)
紅黑樹是每個節點都帶有顏色屬性的二叉查找樹，顏色為紅色或黑色。在二叉查找樹強制的一般要求以外，對于任何有效的紅黑樹我們增加了如下的額外要求:
前中后層遍歷
public void preOrder(Node root){ // 前序遍歷,"中左右"if (root != null){System.out.print(root.data + " ");preOrder(root.left);preOrder(root.right);}}public void inOrder(Node root){ // 中序遍歷,"左中右"if (root != null){inOrder(root.left);System.out.print(root.data + " ");inOrder(root.right);}}public void postOrder(Node root){ // 后序遍歷,"左右中"if (root != null){postOrder(root.left);postOrder(root.right);System.out.print(root.data + " ");}}public void floorOrder(Node root){if(root==null) return;Queue<Node> q = new LinkedBlockingQueue<>();q.add(root);while(!q.isEmpty()){Node t = q.poll();System.out.println(t.value);if(t.left!=null)q.add(t.left);if(t.right!=null)q.add(t.right);}}?
總結
以上是生活随笔為你收集整理的Java—Collection、Map、树的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 科目三并不难 盘点科目三技巧
- 下一篇： 通过人行横道线