TreeMap是红黑二叉树的典型实现,打开TreeMap源码:
private transient Entry<k,V> root = null;
root用来存储树的根节点(Entry是TreeMap的内部类())
Entry Code
static final class Entry<K,V> implements Map,Entry<K,V>{ K key; V value; Entry<K,V> left = null; Entry<K,V> right = null; Entry<K,V> parent; boolean color = BLACK; }
属性:
左节点
右节点
父节点
节点颜色---红黑二叉树
TreeMap的put和remove方法大量使用了红黑树的理论---深入学习红黑树理论---在需要排序的Map时才选用TreeMap
Emloyee类:
package collection.map.TreeMap; /* 因为key可以是任意对象,treemap是递增的方式排序 如果key的值为类会如何排序? 新的接口---comparable */ /*定义一个新的类*/ public class Employee implements Comparable<Employee>{ //定义它的属性 int id; String name; double salary; /*以Employee为key,按照salary排序--->需要实现comparable接口*/ /*构造器*/ public Employee(int id, String name, double salary){ super(); this.id = id; this.name = name; this.salary = salary; } /*重写toString方法*/ @Override public String toString(){ return "id:" + id + ",name:" + name + ",salary:" + salary; } /*实现接口当中未实现的方法*/ @Override public int compareTo(Employee o){ //TODO Auto-generated method stub //负数 : 小于, 0 : 等于, 正数 : 大于--->1 -1 0代替 //比较salary if (salary > o.salary){ //返回值 return 1; }else if (salary < o.salary){ return -1; }else { //如果工资相等利用id排序 if (this.id > o.id){ return 1; }else if (this.id < o.id){ return -1; }else { return 0; //相等 } } } }
TreeMap类:
package collection.map.TreeMap; import java.util.Map; /** * 测试TreeMap的使用 * @author Lucifer */ public class TreeMap { public static void main(String[] args) { //新建Map对象 Map<Integer,String> treemap1 = new java.util.TreeMap<>(); //利用put方法往里面放入链表 treemap1.put(20,"aa"); treemap1.put(3,"bb"); treemap1.put(6,"cc"); /*对Map进行遍历---对链表遍历(可以使用增强for循环)*/ //按照key递增的方式进行排序 for (Integer key : treemap1.keySet()){ //keySet返回的是一个Set集合,放到临时变量里面 System.out.println(key + "---" + treemap1.get(key)); //打印结果按照key递增的方式进行排序然后打印出来 } /*定义一个新的对象---新的Map*/ Map<Employee, String> treemap2 = new java.util.TreeMap<>(); //put方法往里面添加链表内容 treemap2.put(new Employee(100,"Lucifer",100000),"他好坏呀!"); treemap2.put(new Employee(200,"James",90000),"还可以!"); treemap2.put(new Employee(300,"Harden",80000),"真不戳!"); treemap2.put(new Employee(400,"Kevin",80000),"我带你们打!"); //薪水相同会按照id递增的方式排序 /*在进行一个排序--->按照key递增进行排序--->key是Employee对象--->Employee对象递增的方法(Employee类定义了)*/ for (Employee key : treemap2.keySet()){ System.out.println(key + "---" + treemap2.get(key)); } } }
map接口有一个子类叫hashtable
特点:
hashmap是一个map接口的实现类!!!!!
hashmap采用hash算法实现,是map接口最常用的实现类!!!
hashmap在查找、删除、修改方面都有非常高的效率
HashMap:线程不安全、效率高、允许key或value为null
HashTable:线程安全、效率低、不允许key或value为null
如果key是一个类那么就要实现compareble接口