数据结构之 LinkedHashMap 与 TreeMap
一、LinkedHashMap
LinkedHashMap和HashMap区别？
LinkedHashMap底层实现？
利用LinkedHashMap实现LRU缓存？
1. LinkedHashMap和HashMap区别
大多数情况下，只要不涉及线程安全问题，Map基本都可以使用HashMap，不过HashMap有一个问题，就是迭代HashMap的顺序并不是HashMap放置的顺序，也就是无序。HashMap的这一缺点往往会带来困扰，因为有些场景，我们期待一个有序的Map.这就是我们的LinkedHashMap,看个小Demo:
public static void main(String[] args) {
Map<String, String> map = new LinkedHashMap<String, String>();
map.put("apple", "苹果");
map.put("watermelon", "西瓜");
map.put("banana", "香蕉");
map.put("peach", "桃子");
Iterator iter = map.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
System.out.println(entry.getKey() + "=" + entry.getValue());
}
}
输出为：
apple=苹果
watermelon=西瓜
banana=香蕉
peach=桃子可以看到，在使用上，LinkedHashMap和HashMap的区别就是LinkedHashMap是有序的。 上面这个例子是根据插入顺序排序。此外，LinkedHashMap还有一个参数决定是否在此基础上再根据访问顺序(get,put)排序,记住，是在插入顺序的基础上再排序，后面看了源码就知道为什么了。看下例子:
public static void main(String[] args) {
Map<String, String> map = new LinkedHashMap<String, String>(16,0.75f,true);
map.put("apple", "苹果");
map.put("watermelon", "西瓜");
map.put("banana", "香蕉");
map.put("peach", "桃子");
map.get("banana");
map.get("apple");
Iterator iter = map.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
System.out.println(entry.getKey() + "=" + entry.getValue());
}
}
输出为：
watermelon=西瓜
peach=桃子
banana=香蕉
apple=苹果可以看到香蕉和苹果在原来排序的基础上又进行了排序。
二、TreeMap
TreeMap排序规则
TreeMap 默认排序规则:按照key的字典顺序来排序(升序) 。当然,也可以自定义排序规则：实现Comparable接口或者在创建构造器的时候给一个Comparator实例。我们每一种情况都分析一下。
采用默认排序
观察put(key,val)方法，如果key是String类型，则会调用String类中的compareTo做排序。
//String中的 compareTo 方法
public int compareTo(String anotherString) {
int len1 = value.length;
int len2 = anotherString.value.length;
int lim = Math.min(len1, len2);
char v1[] = value;
char v2[] = anotherString.value;
int k = 0;
while (k < lim) {
//将key转为char数组，并根据char的大小来进行判断
char c1 = v1[k];
char c2 = v2[k];
// 两个字符串前面的字符，如果遇到第一个不相等的，就直接返回 字符的ASCll差值。
if (c1 != c2) {
return c1 - c2;
}
k++;
}
// 两个字符串前面的字符相同时，就返回两个字符串长度的差值。
return len1 - len2;
}
//测试代码如下：
TreeMap<String,String> map = new TreeMap<>();
map.put("jack","good");
map.put("bob","nice");
System.out.println(map.toString());
//输出内容为：
{bob=nice, jack=good}调换上面的put顺序为
map.put("bob","nice");
map.put("jack","good");
//输出内容为：
{bob=nice, jack=good}以上结果说明默认的排序规则是根据key值的首字符去进行比较判断的，并按照从小到大升序排序。注意：使用TreeMap时，所有的key都必须直接或间接的实现Comparable接口，否则会报cannot be cast to java.lang.Comparable。当然，直接采用TreeMap(Comparator<? super K> comparator)构造器也是可以的。
采用Comparable接口排序
将key实现Comparable接口，重写其中的compareTo方法，定义排序的规则。我们建一个学生类并按照年龄排序。
class Student implements Comparable<Student>{
String name;
int age;
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
@Override
public int compareTo(Student o) {
if(this.age<o.age){
return -1;
}else if(this.age>o.age){
return 1;
}
return 0;
}
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
}上面规则是：当前元素小于比较元素，则返回-1，大于则返回1，否则返回0。按照TreeMap的put方法逻辑，小于0的则排在左侧，大于的排在右侧，等于的就覆盖，也就实现了升序排序，所以说，当我们想要降序排的时候，只需把自定义中的返回-1和1的替换即可。下面是put源码的部分逻辑：
do {
parent = t;
cmp = k.compareTo(t.key);//调用我们实现的规则
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
测试代码如下：
public class TreeMapTest {
public static void main(String[] args) {
TreeMap<Student,Integer> map = new TreeMap<>();
for(int i=0;i<5;i++){
Student student = new Student();
student.setName("A"+new Random().nextInt(100));
//用来判断相等的情况
if(i>=3){
student.setAge(8);
}
else
student.setAge(new Random().nextInt(30));
map.put(student,Integer.valueOf(i));
}
for(Map.Entry< Student,Integer> entry:map.entrySet()){
System.out.println(entry.getKey()+"--->"+entry.getValue());
}
}
}
//执行结果如下：
Student{name='A3', age=4}--->2
Student{name='A81', age=8}--->4
Student{name='A60', age=9}--->1
Student{name='A4', age=16}--->0从结果可以发现，如果年龄值相等，等于3的已经被等于4的覆盖掉了。
采用Comparator接口排序
当我们并不想把key值拿来实现Comparable接口时，可以在创建TreeMap对象的时候传入排序规则，也就是实现了Comparator接口。
public class TreeMapTest01 {
public static void main(String[] args) {
TreeMap<Computer,String> map = new TreeMap<>(new Comparator<Computer>() {
@Override
public int compare(Computer o1, Computer o2) {
if(o1.id>o2.id){
return 1;
}else if(o1.id<o2.id){
return -1;
}
return 0;
}
});
map.put(new Computer("er",1),"er");
map.put(new Computer("lenovo",2),"lenovo");
System.out.println(map.toString());
}
}
class Computer{
String name;
int id;
public Computer(String name,int id){
this.name=name;
this.id=id;
}
@Override
public String toString() {
return "Computer{" +
"name='" + name + '\'' +
", id=" + id +
'}';
}
}上面的测试类是根据Computer的id进行排序，通过匿名内部类的方式去实现。如果仅是单一的规则这样写没有什么不好，有时候我们 需要根据不同规则维度去进行排序，这样写也不美观，最好的就是写不同的规则类，到时候需要哪一种直接用就好了。改造上面的方法如下：
public class TreeMapTest01 {
public static void main(String[] args) {
TreeMap<Computer,String> map = new TreeMap<>(new ComputerSort02());
map.put(new Computer("er",1),"er");
map.put(new Computer("lenovo",2),"lenovo");
System.out.println(map.toString());
}
}
class Computer{
String name;
int id;
public Computer(String name,int id){
this.name=name;
this.id=id;
}
@Override
public String toString() {
return "Computer{" +
"name='" + name + '\'' +
", id=" + id +
'}';
}
}
//我要根据id排
class ComputerSort01 implements Comparator<Computer>{
@Override
public int compare(Computer o1, Computer o2) {
if(o1.id>o2.id){
return 1;
}else if(o1.id<o2.id){
return -1;
}
return 0;
}
}
//我要根据name长度排
class ComputerSort02 implements Comparator<Computer>{
@Override
public int compare(Computer o1, Computer o2) {
if(o1.name.equals(o2.name))
return 0;
return o1.name.length()- o2.name.length();
}
}出现的坑
map中出现重复键
如果发现自己的map中出现了key相同的情况，那么就得仔细看自己的排序规则是不是写得有问题，只要记住put中的规则是：返回-1往左靠，返回1往又靠，返回0就覆盖，就不会有错。所以key有重复的原因就是因为规则中判断相等的时候没有返回0。
map明明有值，却返回null
出现个问题的原因也是由上面造成的，map中的get方法也是通过compare去获取数据，只有返回为0的时候才能取到数据，否则就会返回null。部分源码如下：
final Entry<K,V> getEntryUsingComparator(Object key) {
@SuppressWarnings("unchecked")
K k = (K) key;
Comparator<? super K> cpr = comparator;
if (cpr != null) {
Entry<K,V> p = root;
while (p != null) {
int cmp = cpr.compare(k, p.key);//自定义的比较器
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p; //只有在相等的时候才会返回
}
}
return null;
}再说TreeMap
TreeMap的底层是通过红黑树实现，红黑树的原理就不做介绍了，我们在put元素的时候会去通过二分法查找是否有相同的key,没有则会将该元素放在红黑树的一个子节点上，然后通过红黑树的自平衡处理来生成一个有序树。在通过get去获取元素的时候，也通过二分法去树的节点上查找，直到找到自己的节点，通过key比较返回0则表示已查找到，返回value值,否则返回null。