關(guān)于算法中的Map的理解典型的計(jì)算用戶輸入的字符出現(xiàn)頻率最高的算法
首先了解下Map：

在講解Map排序之前，我們先來稍微了解下map。map是鍵值對(duì)的集合接口，它的實(shí)現(xiàn)類主要包括：HashMap,TreeMap,Hashtable以及LinkedHashMap等。其中這四者的區(qū)別如下（簡單介紹）：

   HashMap：我們最常用的Map，它根據(jù)key的HashCode 值來存儲(chǔ)數(shù)據(jù),根據(jù)key可以直接獲取它的Value，同時(shí)它具有很快的訪問速度。HashMap最多只允許一條記錄的key值為Null(多條會(huì)覆蓋);允許多條記錄的Value為 Null。非同步的。

  TreeMap: 能夠把它保存的記錄根據(jù)key排序,默認(rèn)是按升序排序，也可以指定排序的比較器，當(dāng)用Iterator 遍歷TreeMap時(shí)，得到的記錄是排過序的。TreeMap不允許key的值為null。非同步的。

  Hashtable: 與 HashMap類似,不同的是:key和value的值均不允許為null;它支持線程的同步，即任一時(shí)刻只有一個(gè)線程能寫Hashtable,因此也導(dǎo)致了Hashtale在寫入時(shí)會(huì)比較慢。

  LinkedHashMap: 保存了記錄的插入順序，在用Iterator遍歷LinkedHashMap時(shí)，先得到的記錄肯定是先插入的.在遍歷的時(shí)候會(huì)比HashMap慢。key和value均允許為空，非同步的。

-方法一

static void doString(String input) {
    Map<Character, Integer> result = new HashMap<Character, Integer>();

    for (int i = 0; i < input.length(); i++) {
        char key = input.charAt(i);
        if (result.containsKey(key)) {
            result.put(key, result.get(key) + 1);
        } else {
            result.put(key, +1);
        }
    }

    System.out.println(result); //輸出產(chǎn)生的 HashMap


    //CompareCount構(gòu)造函數(shù)需要原來的 HashMap 作為參數(shù)
    CompareCount cp = new CompareCount(result);

    TreeMap<Character, Integer> sorted = new TreeMap<Character, Integer>(cp); //根據(jù) Comparator 產(chǎn)生相應(yīng)的 TreeMap

    //添加進(jìn)去，會(huì)依照Comparator產(chǎn)生的大小
    sorted.putAll(result);

    System.out.println(sorted);
    System.out.println(sorted.get('f'));
}

class CompareCount implements Comparator<Character> {

    private Map map;

    public CompareCount(Map map) {
        this.map = map;
    }

    //根據(jù) key 得到相應(yīng)的 value，比較大小
    public int compare(Character o1, Character o2) {

        return (Integer) map.get(o1) < (Integer) map.get(o2) ? -1
                : (Integer) map.get(o1) > (Integer) map.get(o2) ? 1 : 0;
    }
}
output 
{f=1, v=1, d=2, s=1, c=1, a=3, z=1}
{f=1, d=2, a=3}
1
由輸出可以看出，因?yàn)镃omparator比較的是 value，value 相同的不會(huì)被加到 Map 里。Map本來規(guī)定是key 不同，值可以相同。所以這種方法對(duì)于有多個(gè)相同值的 Map 不適用

• 方法2

static void doString(String input) {
    Map<Character, Integer> result = new HashMap<Character, Integer>();

    for (int i = 0; i < input.length(); i++) {
        char key = input.charAt(i);
        if (result.containsKey(key)) {
            result.put(key, result.get(key) + 1);
        } else {
            result.put(key, +1);
        }
    }

    System.out.println(result);

    result = sortByValues(result);
    System.out.println(result);

    // CompareCount cp = new CompareCount(result);
    //
    // TreeMap<Character, Integer> sorted = new TreeMap<Character,
    // Integer>(cp);
    // sorted.putAll(result);
    //
    // System.out.println(sorted);
    // System.out.println(sorted.get('f'));
}

private static Map sortByValues(Map<Character, Integer> result) {

    List<Entry<Character, Integer>> list = new ArrayList<Entry<Character, Integer>>(result.entrySet());
    //根據(jù)制定的Comparator排序，通過 Entry 進(jìn)行排序，雖然也是比較的 value，但是 List 允許重復(fù)的
    Collections.sort(list, new Comparator<Entry<Character, Integer>>() {

        public int compare(Entry<Character, Integer> o1, Entry<Character, Integer> o2) {
            return o1.getValue() < o2.getValue() ? 1 : o1.getValue() > o2.getValue() ? -1 : 0;
        }
    });

    //按照插入排序，LinkedHashMap
    Map<Character, Integer> sorted = new LinkedHashMap<Character, Integer>();
    for (Entry<Character, Integer> e : list) {
        sorted.put(e.getKey(), e.getValue());

    }

    return sorted;

}
output：
{f=1, v=1, d=2, s=1, c=1, a=3, z=1}
{a=3, d=2, f=1, v=1, s=1, c=1, z=1}
Note 
這種方法就很好，可以看出允許重復(fù)的 value 
public static <T> void sort(List<T> list, Comparator<? super T> c) Collections 的 sort 方法只支持 List，不支持 Collection 
注意< 返回1，>返回-1，所以得到的是倒序

iOS HasMap
NSHashTable
NSHashTable 是 NSSet 的通用版本,和 NSSet/NSMutableSet不同的是,NSHashTable具有以下特性:

NSHashTable是可變的,沒有不可變的對(duì)應(yīng)類
NSHashTable可以持有成員的弱引用
NSHashTable可以在加入成員時(shí)進(jìn)行copy操作
NSHashTable可以存儲(chǔ)任意的指針,通過指針來進(jìn)行相等性和散列檢查
基本用法
NSHashTable *hashTable = [NSHashTable hashTableWithOptions:NSPointerFunctionsCopyIn];
[hashTable addObject:@"hello"];
[hashTable addObject:@10];
[hashTable addObject:@"world"];
[hashTable removeObject:@"world"];
NSLog(@"Members: %@", [hashTable allObjects]);
NSMapTable
NSMapTable是NSDictionary的通用版本,NSMapTable具有下面特性:

NSMapTable是可變的,沒有不可變的類
NSMapTable可以持有鍵和值的弱引用,當(dāng)鍵或值當(dāng)中的一個(gè)被釋放時(shí),整個(gè)這一項(xiàng)就會(huì)被移除掉
NSMapTable可以在加入成員時(shí)進(jìn)行copy操作
NSMapTable可以存儲(chǔ)任意的指針,通過指針來進(jìn)行相等性和散列檢查
基本用法
id delegate = ...;
NSMapTable *mapTable = [NSMapTable mapTableWithKeyOptions:NSMapTableStrongMemory valueOptions:NSMapTableWeakMemory];
[mapTable setObject:delegate forKey:@"foo"];
NSLog(@"Keys: %@", [[mapTable keyEnumerator] allObjects]);
NSPointerArray
NSPointerArray是NSArray的通用版本,NSPointerArray具有下面特性:

和傳統(tǒng)Array一樣,用于有序的插入或移除
與傳統(tǒng)Array不同的是,可以存儲(chǔ)NULL,并且NULL還參與 count的計(jì)算
與傳統(tǒng)Array不同的是, count可以set,如果直接set count,那么會(huì)使用NULL占位
可以使用weak來修飾成員
成員可以是所有指針類型
遵循 NSFastEnumeration,可以通過 for...in來進(jìn)行遍歷
對(duì)比
傳統(tǒng)的集合類型都有哪些短板:

放到集合中的對(duì)象,只能強(qiáng)引用
如果想要弱引用,要先用 NSValue打包
不能放入 nil

總結(jié)
永遠(yuǎn)先從最高的抽象層次去嘗試解決問題
如果碰到的問題包含內(nèi)存管理需求,那么 NSHashTable和 NSMapTable值得一試