想要写个key, value有序的HashMap，出现性能问题，大家帮忙给个主意吧。
先说下我的设计思路:
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，而我现在想要的不是“等于”而是“接近”，也就是如何生成一个有序链表)
分享到：
- 2009-05-22 18:33
- 浏览 13699
- 评论(28)
- 论坛回复 / 浏览 (28 / 19332)
- 查看更多
相关推荐
HashMap是Hashtable的轻量级实现（非线程安全的实现），他们都完成了Map接口，主要区别在于HashMap允许空（null）键值（key）,由于非线程安全，效率上可能高于Hashtable。 HashMap允许将null作为一个entry的key或者...
get(key) -> get value associated with key set(key,value) -> set new element in map by key and value delete(key) -> delete entry by key has(key) -> Returns true/false based on whether the map contains ...
一. 理论准备 ...HashMap的值是没有顺序的，它是按照key的HashCode来实现的，对于这个无序的HashMap我们要怎么来实现排序呢？参照TreeMap的value排序。 Map.Entry返回Collections视图。 二. key排序 Tr
HashMap允许将 null 作为一个 entry 的 key 或者 value，而 Hashtable 不允许。 答案 A B C D 解析 A正确。Map是一个接口，hashtable,hashmap都是它的实现。 B正确。由于Hashtable是线程安全的也是sy
在Java的集合框架中，HashSet，HashMap是用的比较多的一... 《Thinking In Java》里面有一个自己采用二维数组实现的保存key-value的demo，书上也说到性能问题，因为从数据结构的顺序结构的观点来看，常规的线性存储，
1. HashMap几乎可以等价于Hashtable，除了HashMap是非synchronized的，并可以接受null(HashMap可以接受为null的键值(key)和值(value)，而Hashtable则不行)。 2. HashMap是非synchronized，而Hashtable是synchronized...
hashmap是一个key-value键值对的数据结构，从结构上来讲在jdk1.8之前是用数组加链表的方式实现，jdk1.8加了红黑树，hashmap数组的默认初始长度是16，hashmap数组只允许一个key为null，允许多个value为null ...
HashMap 是一个散列表，它存储的内容是键值对(key-value)映射。 HashMap 继承于AbstractMap，实现了Map、Cloneable、java.io.Serializable接口。 HashMap 的实现不是同步的，这意味着它不是线程安全的。它的key、...
HashMap是线程不安全的,并允许null key 和 null value。 HashMap在我当前的jdk版本(11)的默认容量为0,在第一次添加元素的时候才初始化容量为 16, 之后才扩容为原来的2倍。 HashMap的扩容是根据 threshold决定的 : ...
HashMap是基于哈希表实现的，每一个元素是一个key-value对，其内部通过单链表解决冲突问题，容量不足（超过了阀值）时，同样会自动增长。 HashMap是非线程安全的，只是用于单线程环境下，多线程环境下可以采用...
HashMap是Hashtable的轻量级实现（非线程安全的实现），他们都完成了Map接口，主要区别在于HashMap允许空（null）键值（key）,由于非线程安全，效率上可能高于Hashtable。 HashMap允许将null作为一个entry的key或者...
HashMap允许将null作为一个entry的key或者value，而 Hashtable不允许。 HashMap把Hashtable的contains方法去掉了 改成containsvalue 和containsKey。因为contains方法容易让人引起误解。 Hashtable继承自Dictionary...
set ( key , value ) 设置HashMap对象中键的值。 返回HashMap对象。 HashMap . prototype . get ( key ) 返回与键关联的值，如果没有，则返回undefined。 HashMap . prototype . has ( key ) 返回一个布尔值，该...
双列集合HashMap是属于java集合框架3大类接口的Map类， Map接口储存一组成对的键-值对象，提供key(键)到value(值)的映射.Map中的key不要求有序，不允许重复.value同样不要求有序，但允许重复. Iterator接口是...
Redis-Java是一款由Java语言实现的高性能缓存中间件，基于TCP实现客户端与服务端双向通信。 基本功能 客户端、服务端收发字节流 服务端解析字节流，执行...set key value get key list lpush key element [element...]
否则判断桶的第一个位置(有可能是链表、红黑树)的 key 是否为查询的 key，是就直接返回 value。 如果第一个不匹配，则判断它的下一个是红黑树还是链表。 红黑树就按照树的查找方式返回值。 不然就按照链表的方式遍历...
HashMap和HashTable的区别 1、两者父类不同 HashMap是继承自AbstractMap类，而Hashtable...HashMap：key可以为null，但是这样的key只能有一个，因为必须保证key的唯一性；可以有多个key值对应的value为null。 4、安全性
Java HashMap Java 集合框架 HashMap 是一个散列表，它存储的内容是键值对(key-value)映射。 ...HashMap 的 key 与 value 类型可以相同也可以不同，可以是字符串（String）类型的 key 和 value
通俗易懂而不失深度 HashMap解读什么是HashMap什么选择这样的结构呢？原代码分析阈值插入删除查询关键下标的算法写在最后 什么是HashMap HashMap在代码的定义如下，从代码可以看出 HashMap的结构是一个数组。 Node[]...
* put(key, value) 向MAP中增加元素（key, value) * remove(key) 删除指定KEY的元素，成功返回True，失败返回False * get(key) 获取指定KEY的元素值VALUE，失败返回NULL * element(index) 获取指定