Re: [問題] HashMap的問題
※ 引述《TonyQ (骨頭)》之銘言：
: 與其要寫HashMap然後再另外對EntrySet寫Comparator做排序
: 倒不如用 TreeMap (差別只有implements SortedMap) 搭配Comparator
: 效能上會好一點(特別是取多次的時候每次取都要sort一次 ,蠻糟的)
: TreeMap(Comparator<? super K> c)
: Constructs a new, empty map, sorted according to the given
: comparator.
基於和平、愛與正義，昨晚在工作到快要秀逗時拿了這個問題來想了一下，
其實是還可以活用 Tree + HashMap 來達成要求的
不過 HashMap 不能拿來直接用.
public Class HashMapWithTreeSet<K extends Comparable,V extends Comparable>
extends HashMap
{
private TreeMap<K> sortedKeys = new TreeMap<K>();
public HashMapWithTreeSet() {
super();
sortedKeys = new TreeMap<K>(new internalComparator<K>(this));
}
.......
class internalComparator<K extends Comparable> implements Comparator<K> {
HashMapWithTreeSet<K, ? extends Comparable> hash = null;
public internalComparator(HashMapWithTreeSet<K,
? extends Comparable> hash) {
this.hash = hash;
}
public int compare(K k1, K k2) {
Object v1 = hash.get(k1), v2 = hash.get(k2);
if (v1 == null && v2 == null) return 0;
if (v1 == null) return -1;
if (v2 == null) return 1;
int result = hash.get(k1).compareTo(hash.get(k2));
if (result == 0) return k1.compareTo(k2);
return result;
}
}
}
大家應該就知道我想要幹什麼了吧... 嘿嘿嘿... 嘿嘿...
接下來只要 override HashMap 的 put, remove，以及 keySet 就達成目標了 XD
這... 算是旁門左道吧 囧rz
(Ver 1.1 : 改了一下 comparator, 不然在 add 時出現問題...)
(Ver 1.2 : 工作中間再偷懶測試......)
把兩個方法做一下測試...
方法 A : HashMapWithTreeSet
方法 B : 整個 entrySet 抽出用 Collections.sort
1) HashMap 為 HashMap<Integer, String>
2) 準備 1000 個不同長度的 String
3) Randomly 決定 Key
4) Randomly 從 1000 個 String 中抽出一個當 Value
5) Randomly 決定是 put 還是 remove, 把 <key,value> 放入
6) 重覆 (3) - (5) n 次
然後那個把整個 Entry set 抽出來 sort 的方法，每個測試在 (3) - (5)
之間平均重覆 15 次
結果是 A 大勝...
抽插次數 n 超過四萬次之後，A 就永遠都比 B 要快了....
你非得用這麼猥褻的字眼不行嗎 <(＃￣皿￣)╮☆(__ __||)
而且要注意的是，A 的那個方法是任何時候抽出來的 keySet 都是 sorted 的，
而不像 B 只有十五次...
當然若是真的只需要在最後結果有 sorted，那還是用整個抽出來 sort 的方法比較快
[... 唉我怎麼放著工作不做，在這裡搞些有的沒的呢...]
(Ver 1.3 : 哈哈哈，我真無聊)
剛剛想到，如果把 Set<Map.Entry> 轉成 Map.Entry[] 再用 Arrays.sort 會不會
快一點
真的會 @_@
HashMap hm = new HashMap<Integer, String>;
......
Comparator ec = new Comparator<Map.Entry>() { ...... }
Set<Map.Entry> s = hm.entrySet();
Map.Entry[] me = new Map.Entry[s.size()];
s.toArray(me);
Arrays.sort(me, ec);
不過也只能撐到抽插次數十萬左右 (喂!)
Sorting 次數仍維持 15 次
--
《為了要得到真相，就要向原 PO 伸圖》
那就是伸圖魔人的沒圖沒真相原則，那時我們堅信那就是逼逼死的真實
靠么，圖咧？
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 147.8.130.225
※ 編輯: superlubu 來自: 147.8.130.225 (11/21 10:07)
※ 編輯: superlubu 來自: 147.8.130.225 (11/21 10:11)
※ 編輯: superlubu 來自: 147.8.130.225 (11/21 15:19)
※ 編輯: superlubu 來自: 147.8.130.225 (11/21 15:25)
推
11/25 14:46, , 1F
11/25 14:46, 1F
討論串 (同標題文章)