当前位置: 首页 > 工具软件 > Treemap > 使用案例 >

数据结构之 LinkedHashMap 与 TreeMap

秦斌
2023-12-01

一、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。

TreeMap原理实现及常用方法

 类似资料: