很久以來一直在程式碼中使用的比較多的資料清單主要是List,而且都是ArrayList,感覺有這個玩意就夠了。 ArrayList是用來實作動態陣列的包裝工具類,這樣寫程式碼的時候就可以拉進拉出,迭代遍歷,蠻方便的。
也不知道從什麼時候開始慢慢的程式碼中就常常會出現HashMap和HashSet之類的工具類別。應該說HashMap比較多一些,而且還是面試經典題,平常也會多看看。開始用的時候簡單理解就是個鍵值對應表,使用鍵來找資料比較方便。隨後深入了解後發現
這玩意還有點小奧秘,特別是新版的JDK對HashMap的改成樹後,程式碼都有點小複雜咯。
Set開始用的較少,只是無意中在一個程式碼中發現一個TreeSet,發現這個類別可以自帶順利,感覺蠻有點意思,才慢慢的發現這也是個好工具啊。
程式碼寫的多了就感覺到基礎的重要性,所以在此寫一篇小文簡單的整理一下對集合的一些知識。
好了,簡單的整理一下:
•List:即是列表,支援數組、鍊錶的功能,一般都是線性的
•Map:即是映射表,儲存的是鍵與值的對應關係
•Set:即集合的意思,主要用於排重資料及排序
先來看看List
List是用於存放線性資料的一種窗口,例如:用於數組的ArrayList和用於鍊錶的LinkedList。
ArrayList
這是一個數組列表,不過提供了自動擴容的功能,實現List接口,外部操作都是通過接口申明的方法訪問,這樣即安全又方便。
ArrayList的關鍵就是自動擴容,在物件初始化時可以設定初始容量,也可以依照預設的容量。如果對陣列大小沒有特別明確可以不指定初始大小,如果明確的話可以指定一個大小,這樣減少動態擴容時產生的卡頓。說到這就要說一下擴容是怎麼實現的了,看看下面的程式碼:
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); }
grow是在ArrayList在添加元素或一些容易檢查時會觸發的一個方法。主要過程:
1、得到數組的長度,並對其進行右移,這樣就相當於oldCapacity/2,得到新的長度
2、如果這個長度小於最小容量那麼直接就用最小容易
3 、如果大於了最大容易則取一個最大值,這裡會呼叫一個hugeCapacity方法,主要是比較minCapacity與MAX_ARRAY_SIZE的,如果minCapacity大於MAX_ARRAY_SIZE則取Integer.MAX_VALUE,否則就取MAX_ARRAY_SIZE,有趣的是MAX_ARRAYeger_VALUE,否則就取MAX_ARRAY_SIZE,有趣的是MAX_ARRAYeger_ZE_ARRAYeger_ZE_ARRAY .MAX_VALUE - 8;並不知道這樣做的意義是什麼
4、最後就是呼叫一個複製方法將現有數複製到一個新的陣列中。
因為有這個複製過程,如果陣列比較大,那麼老是觸發擴容當然就會出現卡頓的情況。所以如果一開始就知道最大值而且很容易成長到這個值,那麼開始初始化時就指定大小會有一定的作用。
LinkedList
這是針對鍊錶的工具類,鍊錶的優秀是添加刪除啥的比較快,但是查找會慢一些。
至於程式碼好像也沒什麼特別的,就是一串指針連結起來,當然Java中就用物件來代替,建立一個Node的對象,Node本身指向了前一個Node和後一個Node,這就是鍊錶的結構:
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; } }
然後用兩個Node指向頭和尾就完成了,下面的代碼:
/** * 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;
看一個add操作:
/** * 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++; }
過往就是:
1、獲取到最後的Node並放在l中
2.建立一個新的Node,將資料取到這個Node中,建立過程會將新Node的prev指向l,這樣就接上了鏈
3、然後將last指向這個新Node
4、然判斷l是否null,如果是null說明是空鍊錶,新node就是第一個元素,這樣first也要指向newNode
5、如果不為空則將l的next指向newNode
6、累加計數器
再來看看Map
Map是鍵與值做一個映射表的應用,主要的實現類別:HashMap,HashTable,TreeMap
HashMap和HashTable
使用hash演算法進行鍵值映射
HashMap和HashTable
使用hash演算法進行鍵值映射的就是HashMap, HashTable是帶有同步的執行緒安全性的類,它們兩主要的差別就是這個。原理也類似,都是透過桶子+鏈來組合實現。桶子是用來存Key的,而由於Hash碰撞的原因值需要用一個鍊錶來儲存。
•桶的意義在於高效,透過Hash計算可以一步定位
•鍊錶的意義在於訪問重複hash的數據具體的原理以前寫過一篇《學習筆記:Hashtable和HashMap》🎜🎜只不過看JDK1.8的HashMap換了儲存結構,採用紅黑樹的結構,這樣可能是解決鍊錶查找效率問題吧?具體沒有細研究。 🎜🎜TreeMap🎜看过TreeMap的代码后发现还是使用的树结构,红黑树。由于红黑树是有序的,所以自然带排序功能。当然也可通过comparator来指定比较方法来实现特定的排序。
因为采用了树结构存储那么添加和删除数据时会麻烦一些,看一下put的代码:
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; }
1、先是检查根节点是否存在,不存在说明是第一条数据,直接作为树的根
2、判断是否存在比较器,如果存在则使用比较器进行查找数据的存放位置,如果比较器返回结果小于0取左,大于0取右,否则直接替换当前节点的值
3、如果不存在比较器则key直接与节点的key比较,比较和前面方法一样
4、接下来就是在找到的parent上创建一个子节点,并放入左或者右子节点中
5、fixAfterInsertion是对节点进行着色
6、累加器处理
在remove操作时也会有点麻烦,除了删除数据外,还要重新平衡一下红黑树。
另外,TreeMap实现了NavigableMap
最后看看Set
Set主要是两类应用:HashSet和TreeSet。
HashSet
字面意思很明确,使用了Hash的集合。这种集合的特点就是使用Hash算法存数据,所以数据不重复,存取都相对较快。怎么做到的呢?
public boolean add(E e) { return map.put(e, PRESENT)==null; }
原来是存在一个map对象中,再看map是个啥?
private transient HashMap<E,Object> map;
是个HashMap,了解HashMap的就明白,这样的数据是不会重复的。因为存入时是鼗对象本身作为Key来存的,所以在HashMap中只会存在一份。
了解了这点其他的东西就非常明白了。
TreeSet
这个集合是用于对集合进行排序的,也就是除了带有排重的能力外,还可以自带排序功能。只不过看了TreeSet的代码发现,其就是在TreeMap的基础实现的。更准确的说应该是NavigableMap的派生类。默认不指定map情况下TreeSet是以TreeMap为基础的。
public TreeSet() { this(new TreeMap<E,Object>()); }
所以,这里可能更关注的是TreeSet是如何排重呢?看一下add的方法吧:
public boolean add(E e) { return m.put(e, PRESENT)==null; }
和HashSet有点类似,都是基于Map的特性来实现排重。确实简单而且有效。
以上就是小编为大家带来的多用多学之Java中的Set,List,Map详解全部内容了,希望大家多多支持PHP中文网~
更多多用多学之Java中的Set,List,Map详解相关文章请关注PHP中文网!