pos機(jī)怎么集合,常用集合的原理分析

 新聞資訊2  |   2023-05-30 09:36  |  投稿人:pos機(jī)之家

網(wǎng)上有很多關(guān)于pos機(jī)怎么集合,常用集合的原理分析的知識(shí),也有很多人為大家解答關(guān)于pos機(jī)怎么集合的問(wèn)題,今天pos機(jī)之家(m.dsth100338.com)為大家整理了關(guān)于這方面的知識(shí),讓我們一起來(lái)看下吧!

本文目錄一覽:

1、pos機(jī)怎么集合

pos機(jī)怎么集合

五、ConcurrentHashMap

支持線程安全的并發(fā)容器 ConcurrentHashMap,原理和HashMap差不多,區(qū)別就是采用了CAS + synchronized 來(lái)保證并發(fā)安全性putVal 加了同步鎖 synchronized

final V putVal(K key, V value, boolean onlyIfAbsent) { if (key == null || value == null) throw new NullPointerException(); //根據(jù) key 計(jì)算出 hashcode int hash = spread(key.hashCode()); int binCount = 0; for (Node<K,V>[] tab = table;;) { Node<K,V> f; int n, i, fh; // 判斷是否需要進(jìn)行初始化 if (tab == null || (n = tab.length) == 0) tab = initTable(); //f 即為當(dāng)前 key 定位出的 Node,如果為空表示當(dāng)前位置可以寫(xiě)入數(shù)據(jù),利用 CAS 嘗試寫(xiě)入,失敗則自旋保證成功 else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null))) break; // no lock when adding to empty bin } else if ((fh = f.hash) == MOVED) tab = helpTransfer(tab, f); //如果當(dāng)前位置的 hashcode == MOVED == -1,則需要進(jìn)行擴(kuò)容 else { //如果都不滿足,則利用 synchronized 鎖寫(xiě)入數(shù)據(jù) V oldVal = null; // todo put 數(shù)據(jù)的時(shí)候 加入了鎖 synchronized (f) { if (tabAt(tab, i) == f) { if (fh >= 0) { binCount = 1; for (Node<K,V> e = f;; ++binCount) { K ek; if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) { oldVal = e.val; if (!onlyIfAbsent) e.val = value; break; } Node<K,V> pred = e; if ((e = e.next) == null) { pred.next = new Node<K,V>(hash, key, value, null); break; } } } else if (f instanceof TreeBin) { Node<K,V> p; binCount = 2; if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) { oldVal = p.val; if (!onlyIfAbsent) p.val = value; } } else if (f instanceof ReservationNode) throw new IllegalStateException("Recursive update"); } } if (binCount != 0) { //如果數(shù)量大于 TREEIFY_THRESHOLD 則要轉(zhuǎn)換為紅黑樹(shù) if (binCount >= TREEIFY_THRESHOLD) treeifyBin(tab, i); if (oldVal != null) return oldVal; break; } } } addCount(1L, binCount); return null; }get方法

public V get(Object key) { Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek; int h = spread(key.hashCode()); if ((tab = table) != null && (n = tab.length) > 0 && (e = tabAt(tab, (n - 1) & h)) != null) { //根據(jù)計(jì)算出來(lái)的 hashcode 尋址,如果就在桶上那么直接返回值 if ((eh = e.hash) == h) { if ((ek = e.key) == key || (ek != null && key.equals(ek))) return e.val; } //如果是紅黑樹(shù)那就按照樹(shù)的方式獲取值 else if (eh < 0) return (p = e.find(h, key)) != null ? p.val : null; // 就不滿足那就按照鏈表的方式遍歷獲取值 while ((e = e.next) != null) { if (e.hash == h && ((ek = e.key) == key || (ek != null && key.equals(ek)))) return e.val; } } return null; }基本上的變量都是被volatile關(guān)鍵字修飾

transient volatile Node<K,V>[] table; private transient volatile Node<K,V>[] nextTable; private transient volatile long baseCount; ...

volatile關(guān)鍵字 Java多線程的三大核心

1、 原子性 :java原子性和數(shù)據(jù)庫(kù)事務(wù)的原子性差不多,一個(gè)操作要么是全部執(zhí)行成功或者是失敗.

JVM 只保證了基本的原子性,但是類(lèi)似 i++ 之類(lèi)的操作,看著好像是原子的操作,其實(shí)里面涉及到了三個(gè)步驟獲取 i 的值自增在賦值給 i這三個(gè)步驟 要實(shí)現(xiàn)i++ 這樣的原子操作就需要用到 synchronized或者是 了lock進(jìn)行加鎖處理。如果是基礎(chǔ)類(lèi)的自增操作可以使用AtomicInteger 這樣的原子類(lèi)來(lái)實(shí)現(xiàn)(其本質(zhì)是利用了CPU 級(jí)別的 的 CAS 指令來(lái)完成的)。AtomicInteger 是線程安全的其中用的最多的方法就是: incrementAndGet() 以原子的方式自增

2、可見(jiàn)性

現(xiàn)在的計(jì)算機(jī),由于 cpu 直接從 主內(nèi)存中讀取數(shù)據(jù)的效率不高。所以都會(huì)對(duì)應(yīng)的 cpu高速緩存,先將主內(nèi)存中的數(shù)據(jù)讀取到緩存中,線程修改數(shù)據(jù)之后首先更新到緩存中,之后才會(huì)更新到主內(nèi)存。如果此時(shí)還沒(méi)有將數(shù)據(jù)更新到主內(nèi)存其他的線程此時(shí)讀取就是修改之前的數(shù)據(jù)volatile關(guān)鍵字就是用于保存內(nèi)存的可見(jiàn)性,當(dāng)線程A更新了volatite的修飾的變量的話,他會(huì)立即刷新到主線程,并且將其余緩存中該變量的值清空,導(dǎo)致其余線程只能去主內(nèi)存讀取最新的值

*synchronized 和加鎖也能保證可見(jiàn)性,實(shí)現(xiàn)原理就是在釋放鎖之前其余線程是訪問(wèn)不到這個(gè)共享變量的。但是和volatile 相比較起來(lái)開(kāi)銷(xiāo)比較大 !

但是volatile不能夠替換synchronized因?yàn)関olatile 不能夠保證原子性 (要么執(zhí)行成功或者失敗,沒(méi)有中間的狀態(tài))

3、順序性

int a = 100 ; //1int b = 200 ; //2int c = a + b ; //3正常的代碼的執(zhí)行順序應(yīng)該是1》》2》》3。但是有時(shí)候 JVM為了提高整體的效率會(huì)進(jìn)行指令重排導(dǎo)致執(zhí)行順序可能是 2》》1》》3。但是JVM 也不能是 什么都進(jìn)行重排,是在保證最終結(jié)果和代碼順序執(zhí)行結(jié)果是一致的情況下才可能會(huì)進(jìn)行重排重排在單線程中不會(huì)出現(xiàn)問(wèn)題,但是在多線程中就會(huì)出現(xiàn)順序不一致的問(wèn)題java中可以使用 volatile 關(guān)鍵字來(lái)保證順序性,synchronized和lock 也可以來(lái)保證有序性,和保證 原子性的方式一樣,通過(guò)同一段時(shí)間只能一個(gè)線程訪問(wèn)來(lái)實(shí)現(xiàn)的除了 volatile 關(guān)鍵字顯式的保證順序之外,jvm HIA通過(guò) happen-before 原則來(lái)隱式來(lái)保證順序性。volitle的應(yīng)用,主要是在單利,個(gè)人感覺(jué)這是常用的在移動(dòng)端的開(kāi)發(fā)!當(dāng)然可以使用內(nèi)部類(lèi)或者是單利去實(shí)現(xiàn),更多的設(shè)計(jì)模式1、volatile 實(shí)現(xiàn)一個(gè)雙重檢查鎖的單例模式

public class Singleton { private static volatile Singleton singleton; private Singleton() { } public static Singleton getInstance() { if (singleton == null) { synchronized (Singleton.class) { if (singleton == null) { singleton = new Singleton(); } } } return singleton; }}這里的 volatile 關(guān)鍵字主要是為了防止指令重排。 如果不用volatile,singleton = new Singleton();,這段代碼其實(shí)是分為三步:分配內(nèi)存空間。(1)初始化對(duì)象。(2)將 singleton 對(duì)象指向分配的內(nèi)存地址。(3)加上volatile 是為了讓以上的三步操作順序執(zhí)行,反之有可能第三步在第二步之前被執(zhí)行就有可能導(dǎo)致某個(gè)線程拿到的單例對(duì)象還沒(méi)有初始化,以致于使用報(bào)錯(cuò)。2、控制停止線程的標(biāo)記

private volatile boolean flag ; private void run(){ new Thread(new Runnable() { @Override public void run() { doSomeThing(); } }); } private void stop(){ flag = false ; }如果沒(méi)有用volatile 來(lái)修飾flag,就有可能其中一個(gè)線程調(diào)用了 stop()方法修改了flag的值并不會(huì)立即刷新到主內(nèi)存中,導(dǎo)致這個(gè)循環(huán)并不會(huì)立即停止.這里主要利用的是 volatile 的內(nèi)存可見(jiàn)性 .

六、HashSet

HashSet 是一個(gè)不允許存儲(chǔ)重復(fù)元素的集合。HashSet的源碼只有三百多行,原理非常簡(jiǎn)單,主要底層還是HashMap。map 和 PERSENT:

// map :用于存放最終數(shù)據(jù)的。 private transient HashMap<E,Object> map; // Dummy value to associate with an Object in the backing Map // PRESENT :是所有寫(xiě)入 map 的 value 值。 private static final Object PRESENT = new Object();構(gòu)造方法:底層一個(gè)hashMap

public HashSet() { map = new HashMap<>(); }關(guān)鍵的就是這個(gè) add()方法。 可以看出它是將存放的對(duì)象當(dāng)做了 HashMap的健,value 都是相同的 RESENT。由于 HashMap 的 key 是不能重復(fù)的,所以每當(dāng)有重復(fù)的值寫(xiě)入到 HashSet時(shí),value會(huì)被覆蓋,但 key不會(huì)受到影響,這樣就保證了HashSet中只能存放不重復(fù)的元素。

public boolean add(E e) { return map.put(e, PRESENT)==null; }

七、LinkedHashMap

HashMap 是一個(gè)無(wú)序的 Map,每次根據(jù) key 的 hashcode 映射到 Entry 數(shù)組上,所以遍歷出來(lái)的順序并不是寫(xiě)入的順序。 因此 JDK 推出一個(gè)基于HashMap但具有順序的LinkedHashMap來(lái)解決有排序需求的場(chǎng)景。它的底層是繼承于HashMap實(shí)現(xiàn)的,由一個(gè)雙向鏈表所構(gòu)成。LinkedHashMap 的排序方式有兩種:根據(jù)寫(xiě)入順序排序。根據(jù)訪問(wèn)順序排序(LRU底層的原理)。 其中根據(jù)訪問(wèn)順序排序時(shí),每次get都會(huì)將訪問(wèn)的值移動(dòng)到鏈表末尾,這樣重復(fù)操作就能得到一個(gè)按照訪問(wèn)順序排序的鏈表。LinkedHashMap中的 Entry:利用了頭節(jié)點(diǎn)和其余的各個(gè)節(jié)點(diǎn)之間通過(guò) Entry中的 after和 before指針進(jìn)行關(guān)聯(lián)變量構(gòu)造方法,LRUchace最近最少使用的緩存底層就是這個(gè)構(gòu)造函數(shù)。

public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder; }側(cè)重關(guān)注 put,會(huì)走父類(lèi)HashMap中的put方法,具體請(qǐng)看HashMap put 方法的解釋1、 在 LinkedHashMap 重寫(xiě)了,newNode的方法。 使用了LinkedHashMap.Entry里面多了兩個(gè)結(jié)點(diǎn) Entry<K,V> before, after;

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) { LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e); //秘密就在于 new的是自己的Entry類(lèi),然后調(diào)用了linkedNodeLast linkNodeLast(p); return p;}2、實(shí)現(xiàn)了afterNodeAccess()方法, void afterNodeAccess(Node<K,V> p) { }!此函數(shù)執(zhí)行的效果就是將最近使用的Node,放在鏈表的最末尾。特別說(shuō)明一下,這里是顯示鏈表的修改后指針的情況,實(shí)際上在桶里面的位置是不變的,只是前后的指針指向的對(duì)象變了!

// 此函數(shù)執(zhí)行的效果就是將最近使用的Node,放在鏈表的最末尾void afterNodeAccess(Node<K,V> e) { // move node to last LinkedHashMap.Entry<K,V> last; //僅當(dāng)按照LRU原則且e不在最末尾,才執(zhí)行修改鏈表,將e移到鏈表最末尾的操作 if (accessOrder && (last = tail) != e) { //將e賦值臨時(shí)節(jié)點(diǎn)p, b是e的前一個(gè)節(jié)點(diǎn), a是e的后一個(gè)節(jié)點(diǎn) LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; //設(shè)置p的后一個(gè)節(jié)點(diǎn)為null,因?yàn)閳?zhí)行后p在鏈表末尾,after肯定為null p.after = null; //p前一個(gè)節(jié)點(diǎn)不存在,情況一 if (b == null) head = a; else b.after = a; if (a != null) a.before = b; //p的后一個(gè)節(jié)點(diǎn)不存在,情況二 else last = b; if (last == null) head = p; else { //正常情況,將p設(shè)置為尾節(jié)點(diǎn)的準(zhǔn)備工作,p的前一個(gè)節(jié)點(diǎn)為原先的last,last的after為p p.before = last; last.after = p; } //將p設(shè)置為將p設(shè)置為尾節(jié)點(diǎn) tail = p; ++modCount; // 修改計(jì)數(shù)器+1 }}3、 put方法 執(zhí)行的第二個(gè)步驟 ,這個(gè)方法沒(méi)什么用盡可能刪除最老的 插入后把最老的Entry刪除,不過(guò)removeEldestEntry總是返回false,所以不會(huì)刪除,估計(jì)又是一個(gè)方法給子類(lèi)用的

void afterNodeInsertion(boolean evict) { // possibly remove eldest LinkedHashMap.Entry<K,V> first; if (evict && (first = head) != null && removeEldestEntry(first)) { K key = first.key; // todo hashmap中移除 Node結(jié)點(diǎn) removeNode(hash(key), key, null, false, true); }} // 如果映射表示緩存,這是有用的:它允許通過(guò)刪除過(guò)時(shí)條目來(lái)減少內(nèi)存消耗的映射。protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { return false;}4 、afterNodeRemoval()移除結(jié)點(diǎn)也會(huì)重寫(xiě),因?yàn)榻Y(jié)點(diǎn)都不一樣

void afterNodeRemoval(Node<K,V> e) { // unlink //與afterNodeAccess一樣,記錄e的前后節(jié)點(diǎn)b,a LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; //p已刪除,前后指針都設(shè)置為null,便于GC回收 p.before = p.after = null; //與afterNodeAccess一樣類(lèi)似,一頓判斷,然后b,a互為前后節(jié)點(diǎn) if (b == null) head = a; else b.after = a; if (a == null) tail = b; else a.before = b;}get()方法詳情,然后調(diào)用父類(lèi)HashMap 的getNode()去找結(jié)點(diǎn)

public V get(Object key) { Node<K,V> e; //調(diào)用HashMap的getNode的方法, if ((e = getNode(hash(key), key)) == null) return null; if (accessOrder) afterNodeAccess(e); return e.value; }HashMap中的getNode() 方法

final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; if ((e = first.next) != null) { if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; }關(guān)于訪問(wèn)順序排序的Demo,我只想說(shuō)明了一下,等于用了的數(shù)據(jù),就會(huì)放在鏈表的末尾,這個(gè)類(lèi)也是安卓中LruCache的底層原理

LinkedHashMap<String, Integer> map1 = new LinkedHashMap<String, Integer>(10, (float) 0.75,true); map1.put("1",1) ; map1.put("2",2) ; map1.put("3",3) ; map1.put("4",4) ; map1.put("5",5) ; map1.put("6",6) ; map1.put("7",7) ; map1.put("8",8) ; map1.put("9",9) ; map1.put("10",10) ; map1.get("6"); // {1=1, 2=2, 3=3, 4=4, 5=5, 7=7, 8=8, 9=9, 10=10, 6=6} System.out.println("map1=="+map1);

LinkedHashMap的原理

八、LruCache

Android中提供了一種基本的緩存策略,即LRU(least recently used)?;谠摲N策略,當(dāng)存儲(chǔ)空間用盡時(shí),緩存會(huì)清除最近最少使用的對(duì)象LRU(Least Recently Used)最近最少使用的,看了源碼才知道核心是LRUCache類(lèi),這個(gè)類(lèi)的核心其實(shí)是 LinkedHashMap類(lèi).Demo 如下

LruCache<Integer,String> lruCache=new LruCache<>(5); lruCache.put(1,"1"); lruCache.put(2,"2"); lruCache.put(3,"3"); lruCache.put(4,"4"); lruCache.put(5,"5"); lruCache.get(1); lruCache.get(2); lruCache.get(3); lruCache.get(4); Map<Integer, String> snapshot = lruCache.snapshot(); //lruCache={5=5, 1=1, 2=2, 3=3, 4=4} 5最少使用到 System.out.println("lruCache="+snapshot.toString()); //當(dāng)多添加一個(gè)的話,那么5就會(huì)被刪除,加入6上去 lruCache.put(6,"6"); // new lruCache={1=1, 2=2, 3=3, 4=4, 6=6} Map<Integer, String> snapshot1 = lruCache.snapshot(); System.out.println(" new lruCache="+snapshot1.toString());構(gòu)造方法,可以明顯看出,底層使用的是LinkedHashMap. public LruCache(int maxSize) { if (maxSize <= 0) { throw new IllegalArgumentException("maxSize <= 0"); } this.maxSize = maxSize; // 初始化這里 就是 new的 true的 所以使用的順序排序 this.map = new LinkedHashMap<K, V>(0, 0.75f, true); }put方法 :重要的就是在添加過(guò)緩存對(duì)象后,調(diào)用trimToSize()方法,來(lái)判斷緩存是否已滿,如果滿了就要?jiǎng)h除近期最少使用的算法.同時(shí)線程也是安全的。

public final V put(K key, V value) { //不可為空,否則拋出異常 if (key == null || value == null) { throw new NullPointerException("key == null || value == null"); } V previous; // 多線程 可以使用 synchronized (this) { //插入的緩存對(duì)象值加1 putCount++; //增加已有緩存的大小 size += safeSizeOf(key, value); //向map中加入緩存對(duì)象 previous = map.put(key, value); if (previous != null) { //如果已有緩存對(duì)象,則緩存大小恢復(fù)到之前 size -= safeSizeOf(key, previous); } } //entryRemoved()是個(gè)空方法,可以自行實(shí)現(xiàn) if (previous != null) { entryRemoved(false, key, previous, value); } //調(diào)整緩存大小(關(guān)鍵方法) trimToSize(maxSize); return previous; }1、safeSizeOf方法,這個(gè)sizeof的方法,就是我們自己需要重寫(xiě)的,記得圖片加載框架的設(shè)計(jì),就會(huì)運(yùn)用到他

private int safeSizeOf(K key, V value) { // 每一個(gè)的需要緩存的大小 int result = sizeOf(key, value); if (result < 0) { throw new IllegalStateException("Negative size: " + key + "=" + value); } return result; } protected int sizeOf(K key, V value) { return 1; }2、調(diào)整緩存大小(關(guān)鍵方法) trimToSize(maxSize); maxSize也就是指定的大小,當(dāng)if (size <= maxSize) { break; }這個(gè)判斷不成立的時(shí)候,就會(huì)往下走,迭代器就會(huì)去獲取第一個(gè)對(duì)象,即隊(duì)尾的元素,近期最少訪問(wèn)的元素。然后把它刪除該對(duì)象,并更新緩存大小 map.remove(key);

private void trimToSize(int maxSize) { while (true) { K key; V value; synchronized (this) { if (size < 0 || (map.isEmpty() && size != 0)) { throw new IllegalStateException(getClass().getName() + ".sizeOf() is reporting inconsistent results!"); } if (size <= maxSize) { break; } //迭代器獲取第一個(gè)對(duì)象,即隊(duì)尾的元素,近期最少訪問(wèn)的元素 Map.Entry<K, V> toEvict = null; for (Map.Entry<K, V> entry : map.entrySet()) { toEvict = entry; } if (toEvict == null) { break; } key = toEvict.getKey(); value = toEvict.getValue(); //刪除該對(duì)象,并更新緩存大小 map.remove(key); size -= safeSizeOf(key, value); evictionCount++; } // 空實(shí)現(xiàn) entryRemoved(true, key, value, null); } }關(guān)于 get方法!也是一個(gè)同步的方法。

public final V get(K key) { //key為空拋出異常 if (key == null) { throw new NullPointerException("key == null"); } V mapValue; synchronized (this) { //獲取對(duì)應(yīng)的緩存對(duì)象 //get()方法會(huì)實(shí)現(xiàn)將訪問(wèn)的元素更新到隊(duì)列頭部的功能 // todo LinkedHashMap 里面已經(jīng)實(shí)現(xiàn)了 如果 添加到頭部去 mapValue = map.get(key); if (mapValue != null) { hitCount++; return mapValue; } missCount++; } ...}LruCache使用的Demo,這個(gè) Demo 就看看,沒(méi)吊用。

public class ImageCache { //定義LruCache,指定其key和保存數(shù)據(jù)的類(lèi)型 private LruCache<String, Bitmap> mImageCache; ImageCache() { //獲取當(dāng)前進(jìn)程可以使用的內(nèi)存大小,單位換算為KB final int maxMemory = (int)(Runtime.getRuntime().maxMemory() / 1024); //取總內(nèi)存的1/4作為緩存 final int cacheSize = maxMemory / 4; //初始化LruCache mImageCache = new LruCache<String, Bitmap>(cacheSize) { //定義每一個(gè)存儲(chǔ)對(duì)象的大小 @Override protected int sizeOf(String key, Bitmap bitmap) { return bitmap.getRowBytes() * bitmap.getHeight() / 1024; } }; } //獲取數(shù)據(jù) public Bitmap getBitmap(String url) { return mImageCache.get(url); } //存儲(chǔ)數(shù)據(jù) public void putBitmap(String url, Bitmap bitmap) { mImageCache.put(url, bitmap); } }

九、SparseArray

SparseArray是android里為<Interger,Object> 這樣的Hashmap而專門(mén)寫(xiě)的類(lèi),目的是提高效率,其核心是折半查找函數(shù)(binarySearch)。SparseArray僅僅提高內(nèi)存效率,而不是提高執(zhí)行效率,所以也決定它只適用于android系統(tǒng)(內(nèi)存對(duì)android項(xiàng)目有多重要)SparseArray不需要開(kāi)辟內(nèi)存空間來(lái)額外存儲(chǔ)外部映射,從而節(jié)省內(nèi)存。變量,核心就是兩個(gè)數(shù)組:mKeys mValues

//是否可以回收,即清理mValues中標(biāo)記為DELETED的值的元素 private boolean mGarbage = false; private int[] mKeys; //保存鍵的數(shù)組 private Object[] mValues; //保存值的數(shù)組 private int mSize; //當(dāng)前已經(jīng)保存的數(shù)據(jù)個(gè)數(shù)構(gòu)造方法 :如果initialCapacity=0那么mKeys,mValuse都初始化為size=0的數(shù)組,當(dāng)initialCapacity>0時(shí),系統(tǒng)生成length=initialCapacity的value數(shù)組,同時(shí)新建一個(gè)同樣長(zhǎng)度的key數(shù)組。

public SparseArray() { this(10); } public SparseArray(int initialCapacity) { if (initialCapacity == 0) { mKeys = EmptyArray.INT; mValues = EmptyArray.OBJECT; } else { /* ArrayUtils.newUnpaddedObjectArray 的源碼 public static Object[] newUnpaddedObjectArray(int minLen) { return (Object[])VMRuntime.getRuntime().newUnpaddedArray(Object.class, minLen); } */ mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity); mKeys = new int[mValues.length]; } mSize = 0; }關(guān)于put方法,關(guān)鍵是通過(guò)二分查找,查找相對(duì)應(yīng)的i角標(biāo),如果存在的話,直接賦值新的值,如果不存在的話,取 ~i 位非運(yùn)算符(~): 十進(jìn)制變二進(jìn)制:原碼--反碼--加一(補(bǔ)碼),相當(dāng)于 value +1 然后 取反 就可以了.然后就會(huì)走到 mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);和 mValues = GrowingArrayUtils.insert(mValues, mSize, i, value); 中,這樣就完成了賦值的過(guò)程。

public void put(int key, E value) { // 二分查找,這個(gè)i的值, int i = ContainerHelpers.binarySearch(mKeys, mSize, key); //如果找到了,就把這個(gè)值給替換上去 ,或者是賦值上去 // 這里 也就可以解釋出為啥 替換為最新的值 if (i >= 0) { mValues[i] = value; } else { //這里就是key要插入的位置,上面二分查找方法提到過(guò) //位非運(yùn)算符(~) i = ~i; if (i < mSize && mValues[i] == DELETED) { mKeys[i] = key; mValues[i] = value; return; } if (mGarbage && mSize >= mKeys.length) { gc(); // Search again because indices may have changed. i = ~ContainerHelpers.binarySearch(mKeys, mSize, key); } // 一個(gè)新的值 ,就會(huì)把key 和 value 和 i值插入到兩個(gè)數(shù)組中 mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key); mValues = GrowingArrayUtils.insert(mValues, mSize, i, value); // todo 然后長(zhǎng)度 加上 1 nice mSize++; } }get方法:通過(guò)二分查找法,在mKeys數(shù)組中查詢key的位置,然后返回mValues數(shù)組中對(duì)應(yīng)位置的值,找不到則返回默認(rèn)值

public E get(int key, E valueIfKeyNotFound) { // 二分查找 感覺(jué)不像啊 臥槽 int i = ContainerHelpers.binarySearch(mKeys, mSize, key); if (i < 0 || mValues[i] == DELETED) { return valueIfKeyNotFound; } else { return (E) mValues[i]; } }delete其實(shí)就是把這個(gè) mValues[i]標(biāo)記為 DELETED.

public void delete(int key) { int i = ContainerHelpers.binarySearch(mKeys, mSize, key); /* i>0表示,找到了key對(duì)應(yīng)的下標(biāo),否則應(yīng)該是負(fù)數(shù)。同時(shí)判斷mValues[i] 是不是Object這個(gè)對(duì)象,如果不是,直接替換為Object(DELETE起到標(biāo)記刪除位置的作用),并標(biāo)記 mGarbage=true,注意:這里delete只操作了values數(shù)組,并沒(méi)有去操作key數(shù)組; */ if (i >= 0) { if (mValues[i] != DELETED) { mValues[i] = DELETED; mGarbage = true; } } }removeReturnOld 其實(shí)就是多了一步,把要?jiǎng)h除的值返回,其余同delete一樣

public E removeReturnOld(int key) { int i = ContainerHelpers.binarySearch(mKeys, mSize, key); if (i >= 0) { if (mValues[i] != DELETED) { final E old = (E) mValues[i]; mValues[i] = DELETED; mGarbage = true; return old; } } return null; }clear 這里要留意,clear只是清空了values數(shù)組,并沒(méi)有操作keys數(shù)組,這里也是傳遞的地址值,然后通過(guò)for循環(huán),把每個(gè)元素清空!

public void clear() { int n = mSize; Object[] values = mValues; for (int i = 0; i < n; i++) { values[i] = null; } mSize = 0; mGarbage = false; }其實(shí)還有個(gè)方法append,添加數(shù)據(jù)的時(shí)候最好去使用它,因?yàn)樗鼤?huì)判斷下mSize != 0 && key <= mKeys[mSize - 1]、如果滿足了才會(huì)調(diào)用 put方法,不滿足,直接添加數(shù)據(jù),而不是一上來(lái)就開(kāi)始進(jìn)行二分查找。

// 要使用這個(gè)方法 好點(diǎn) 。 public void append(int key, E value) { // 判斷了是否 需要 二分查找,還是直接插入 if (mSize != 0 && key <= mKeys[mSize - 1]) { put(key, value); return; } if (mGarbage && mSize >= mKeys.length) { // 通過(guò)gc的方法,把DELETED值的 values 清空 gc(); } // 可以直接都要這里來(lái) ,是最節(jié)約能量 mKeys = GrowingArrayUtils.append(mKeys, mSize, key); mValues = GrowingArrayUtils.append(mValues, mSize, value); mSize++; }關(guān)于原型模式中的深拷貝的實(shí)現(xiàn),這里也幫我指明了,一定要記得拷貝類(lèi)中的容器

@Override @SuppressWarnings("unchecked") public SparseArray<E> clone() { SparseArray<E> clone = null; try { clone = (SparseArray<E>) super.clone(); // 原型模式的深拷貝 兩個(gè)容器的拷貝的過(guò)程----?。?! clone.mKeys = mKeys.clone(); clone.mValues = mValues.clone(); } catch (CloneNotSupportedException cnse) { /* ignore */ } return clone; }其他的 SparseBooleanArray SparseIntArray SparseLongArray 的原理一樣SparseArray與HashMap無(wú)論是怎樣進(jìn)行插入,數(shù)據(jù)量相同時(shí),前者都要比后者要省下一部分內(nèi)存,但是效率呢?----在倒序插入的時(shí)候,SparseArray的插入時(shí)間和HashMap的插入時(shí)間遠(yuǎn)遠(yuǎn)不是一個(gè)數(shù)量級(jí).由于SparseArray每次在插入的時(shí)候都要使用二分查找判斷是否有相同的值被插入.因此這種倒序的情況是SparseArray效率最差的時(shí)候.附贈(zèng)一個(gè)二分查找

/** * 二分查找 * @param ints 需要被查找的數(shù)組 * @param length 數(shù)組的長(zhǎng)度 * @param value 查找的值 */ private int binarySearch(int[] ints, int length, int value) { int i = 0; int h = length - 1; while (i <= h) { /** * >>>與>>唯一的不同是它無(wú)論原來(lái)的最左邊是什么數(shù),統(tǒng)統(tǒng)都用0填充。 * —比如你的例子,byte是8位的,-1表示為byte型是11111111(補(bǔ)碼表示法) * b>>>4就是無(wú)符號(hào)右移4位,即00001111,這樣結(jié)果就是15。 * 這里相當(dāng)移動(dòng)一位,除以二 */ //中間的角標(biāo) final int mid = (i + h) >>> 1;// 第一次 2 第二次 mid=3 第三次mid=4 final int midVal = ints[mid];// 第一次 3 第二次 midVal=4 第三次mid=5 if (midVal < value) { i = mid + 1;// 第一次 3 第二次 i=4 } else if (value < midVal) { h = mid - 1; } else if (value == midVal) { return mid; //第三次mid=5 返回了 } } // 這個(gè)取反 ,相當(dāng)于 value +1 然后 取反 就可以了 return ~value; }附贈(zèng)System.arraycopy() 的用法

int[] mKeys={10,5,14,5,46}; int[] newKeys=new int[5]; /* * @param src 源數(shù)組。 * @param srcPos 表示源數(shù)組要復(fù)制的起始位置, * @param dest 目的地?cái)?shù)組。 * @param destPos 在目標(biāo)數(shù)據(jù)中的起始位置。 * @param length 要復(fù)制的數(shù)組元素的數(shù)目。 */ // todo source of type android.util.SparseArray is not an array // destPsot +length 不能超過(guò) 新的數(shù)組的長(zhǎng)度 System.arraycopy(mKeys,0, newKeys, 2, 3); for (Integer str : newKeys) { System.out.print("newKeys="+str+" "); }

最后說(shuō)明幾點(diǎn)

ArrayList 的主要消耗是數(shù)組擴(kuò)容以及在指定位置添加數(shù)據(jù),在日常使用時(shí)最好是指定大小,盡量減少擴(kuò)容。更要減少在指定位置插入數(shù)據(jù)的操作。ArrayList遍歷的速度快,插入刪除速度慢,隨機(jī)訪問(wèn)的速度快LinkedList 插入,刪除都是移動(dòng)指針效率很高。查找需要進(jìn)行遍歷查詢,效率較低。二分查找,如果查找的index的越接近size的一半的話,這樣查找的效率很低HashMap 是一個(gè)線程不安全的容器,發(fā)生擴(kuò)容時(shí)會(huì)出現(xiàn)環(huán)形鏈表從而導(dǎo)致死循環(huán)HashMap 是一個(gè)無(wú)序的 Map,因?yàn)槊看胃鶕?jù) key的 hashCode映射到Entry 數(shù)組上,所以遍歷出來(lái)的順序并不是寫(xiě)入的順序。HashMap 遍歷的速度慢,底層決定了,插入刪除的速度快,隨機(jī)訪問(wèn)的速度也比較快ConcurrentHashMap 并發(fā)容器,區(qū)別就是采用了CAS + synchronized 來(lái)保證并發(fā)安全性位與運(yùn)算符&,把做運(yùn)算的兩個(gè)數(shù)都轉(zhuǎn)化為二進(jìn)制的,然后從高位開(kāi)始比較,如果兩個(gè)數(shù)都是1則為1,否者為0無(wú)符號(hào)的右移(>>>):按照二進(jìn)制把數(shù)字右移指定數(shù)位,高位直接補(bǔ)零,低位移除!a=a|b 等于 a|=b的意思就是把a(bǔ)和b按位或然后賦值給a 按位或的意思就是先把a(bǔ)和b都換成2進(jìn)制,然后用或操作位異或運(yùn)算(^): 運(yùn)算規(guī)則是兩個(gè)數(shù)轉(zhuǎn)為二進(jìn)制,然后從高位開(kāi)始比較,如果相同則為0,不相同則為1HashSet 底層其實(shí)就是 HashMap,只不過(guò)是一個(gè)value都一樣的HashSet.LRU(Least Recently Used)最近最少使用的,看了源碼才知道核心是LRUCache類(lèi),這個(gè)類(lèi)的核心其實(shí)是 LinkedHashMap類(lèi).~i 位非運(yùn)算符(~): 十進(jìn)制變二進(jìn)制:原碼--反碼--加一(補(bǔ)碼),相當(dāng)于 value +1 然后 取反 就可以了SparseArray SparseBooleanArray SparseIntArray SparseLongArray 的原理一樣SparseArray與HashMap無(wú)論是怎樣進(jìn)行插入,數(shù)據(jù)量相同時(shí),前者都要比后者要省下一部分內(nèi)存,但是效率呢?----在倒序插入的時(shí)候,SparseArray的插入時(shí)間和HashMap的插入時(shí)間遠(yuǎn)遠(yuǎn)不是一個(gè)數(shù)量級(jí).由于SparseArray每次在插入的時(shí)候都要使用二分查找判斷是否有相同的值被插入.因此這種倒序的情況是SparseArray效率最差的時(shí)候.二分查找,是當(dāng)角標(biāo)越接近數(shù)組長(zhǎng)度的一半,效率越低臥槽,剛看了一下總共將近一萬(wàn)字,光寫(xiě)的過(guò)程用了16個(gè)小時(shí),整理資料大概是10個(gè)小時(shí)。

以上就是關(guān)于pos機(jī)怎么集合,常用集合的原理分析的知識(shí),后面我們會(huì)繼續(xù)為大家整理關(guān)于pos機(jī)怎么集合的知識(shí),希望能夠幫助到大家!

轉(zhuǎn)發(fā)請(qǐng)帶上網(wǎng)址:http://m.dsth100338.com/newsone/60337.html

你可能會(huì)喜歡:

版權(quán)聲明:本文內(nèi)容由互聯(lián)網(wǎng)用戶自發(fā)貢獻(xiàn),該文觀點(diǎn)僅代表作者本人。本站僅提供信息存儲(chǔ)空間服務(wù),不擁有所有權(quán),不承擔(dān)相關(guān)法律責(zé)任。如發(fā)現(xiàn)本站有涉嫌抄襲侵權(quán)/違法違規(guī)的內(nèi)容, 請(qǐng)發(fā)送郵件至 babsan@163.com 舉報(bào),一經(jīng)查實(shí),本站將立刻刪除。