精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
---|---|
作者 | 正文 |
发表时间:2009-05-22
先说下我的设计思路: LinkedHashMap里面有一个模拟的“双向循环链表”,用来保存entry的插入顺序,我也可以采用这种方法来在插入的时候保存key和value的有序。 这里暂定名为OrderedHashMap,主要代码是从LinkedHashMap抄过来的,它也维护着两个模拟“双向循环链表”:keyHeader和valueHeader,保持key或value由小到大的顺序。当有个元素put进来后,除把它存在散列桶中外,还要在keyHeader按key的大小插入,也要在valueHeader上按value的顺序插入。 想要输出的话,可以从这两个“头指针”向前或向后来迭代得到key或value有序的entry。 (可以实现key和value,正序逆序的输出,只对数值型比较,如果不是数值型的话,如HashMap般正常处理) 下面是测试结果: Value逆序输出 OrderHashMap<Object, Object> map = new OrderHashMap<Object, Object>(); map.put(8, 1); map.put(9, "value"); map.put(5, 6); map.put("key", 9); Iterator<Map.Entry<Object, Object>> it = map.valueDescendIterator(); while (it.hasNext()) { Map.Entry<Object, Object> key = it.next(); System.out.println(key.getKey() + " " + key.getValue()); } 得到结果 key 9 5 6 8 1 Key逆序输出 OrderHashMap<Object, Object> map = new OrderHashMap<Object, Object>(); map.put(8, 1); map.put(9, "value"); map.put(5, 6); map.put("key", 9); Iterator<Map.Entry<Object, Object>> it = map.keyDescendIterator(); while (it.hasNext()) { Map.Entry<Object, Object> key = it.next(); System.out.println(key.getKey() + " " + key.getValue()); } 得到结果 9 value 8 1 5 6 现在存在的问题: 1.HashMap的key, value都是object,而我现在只想比较数值类型的key或value的对象。对于所有数值型,怎么做个通用的比较方法呢?(我先把它们转成Number类,再强制转成double类型进行比较,总觉的这种方法很山寨)。 2.对象多的时候,插入很慢的。它要从链表头一个接一个的比较对象,速度奇慢无比,怎么能优化下呢?(网上找“查找有序链表”时,都是那个key等于key或value,而我现在想要的不是“等于”而是“接近”,也就是如何生成一个有序链表) 声明:ITeye文章版权属于作者,受法律保护。没有作者书面许可不得转载。
推荐链接
|
|
返回顶楼 | |
发表时间:2009-05-22
TreeMap?
|
|
返回顶楼 | |
发表时间:2009-05-22
dennis_zane 写道 TreeMap?
应该是像LinkedHashMap,里面维护着两个模拟的“双向循环链表”,呵呵 |
|
返回顶楼 | |
发表时间:2009-05-22
1. BigDecimal?
2. 自己实现一个二分查找? 疑问: 为什么put了4次但是输出只有3行? |
|
返回顶楼 | |
发表时间:2009-05-22
rdcyash 写道 1. BigDecimal?
2. 自己实现一个二分查找? 疑问: 为什么put了4次但是输出只有3行? 自己写了个,但是如果不是key相等,而是key相邻的话,可能性太多了,bug频出,最后放弃了。 我只处理“数值型”,所以put的时候分别加了string型的key和value,这样取的时候不会把非数值型的迭代出来。 可以用传统的entrySet来取出所有的entry |
|
返回顶楼 | |
发表时间:2009-05-22
dennis_zane 写道 TreeMap?
嗯,我也这么觉得 |
|
返回顶楼 | |
发表时间:2009-05-22
最后修改:2009-05-22
直接用Hashtable,就能实现K排序,V存值,方便多了
|
|
返回顶楼 | |
发表时间:2009-05-23
wjyjimy 写道 直接用Hashtable,就能实现K排序,V存值,方便多了
我现在也要实现value排序 |
|
返回顶楼 | |
发表时间:2009-05-25
又沉下去了?
顶起 |
|
返回顶楼 | |
发表时间:2009-05-25
BidiMap可以...试试
apache collections |
|
返回顶楼 | |