8.Map

Map集合

特点
     - 存储的是K-V对
     - 无序
     - key唯一    key不能重复，但值可以重复 ，key可以看为Value的索引

常见实现类:

HashMap：底层使用位桶、链表、红黑树实现(红黑树的加入是jdk1.8后，当链表长度超过 阈值(8)时，使用红黑树)，大大减少了查找时间

TreeMap: 底层位红黑树实现

LinkedHashMap：按插入的顺序排列。HashMap和双向链表合二为一就是LinkedHashMap

Hashtable: 和HashMap存储原理相似，但方法都是synchronized,因此时线程安全的，不常用

Map常用方法

HashMap<String,Integer> map=new HashMap<>();
        System.out.println(map.size());//0
        //1.put
        map.put("java",12);
        map.put("c",13);
        map.put("c++",14);
        map.put("php",16);
        map.put("php",18);
        System.out.println(map);//{c++=14, java=12, c=13, php=18}

        HashMap<String,Integer> map2=new HashMap<>();
        System.out.println(map.size());//0
        //1.put
        map2.put("a",22);
        map2.put("b",13);
        map2.put("c",13);
        map2.put("d",26);
        map2.put("e",26);
        System.out.println(map2);//{a=22, b=13, c=24, d=26, e=26}

        //isEmpty():boolean 是否为空
        System.out.println(map.isEmpty());//false

        //containsKey(Object):boolean     Object是对象 是否包含key
        System.out.println(map.containsKey("c++"));//true

        //containsValue(Objects):boolean  是否包含value
        System.out.println(map.containsValue(13));//true

        //get(Object):V  类似peek 根据key打印value 不会减少对象
        System.out.println(map.get("php"));//18
        System.out.println(map);//{c++=14, java=12, c=13, php=18},没有减少对象

        //put(K,V):V 放入key value值
        System.out.println(map.put("c+++",10));//null
        System.out.println(map);

        //remove(Object):V  返回移除的key对应的值
        System.out.println(map.remove("c++"));//14,返回移除的key对应的值
        System.out.println(map);//{java=12, c=13, c+++=10, php=18}

        //putAll
        HashMap<String, Integer> map3 = new HashMap<String, Integer>();
        map3.put("aa",20);
        map3.put("bb",21);
        map3.put("cc",22);
        map.putAll(map3);
        System.out.println();


        //clear();清除所有键值对
        map2.clear();
        System.out.println(map2);//{}

        //keySet:Set<key>返回所有键（key）组成集合set
        System.out.println(map.keySet());//[java, c, c+++, php]

        //values():Collection<V>返回所有值（value）组成的集合Collection
        System.out.println(map.values());//[12, 13, 10, 18]

        //froEach():void 迭代器
        map.forEach(new BiConsumer<String, Integer>() {
            @Override
            public void accept(String s, Integer integer) {
                System.out.println(s);
                System.out.println(integer);
            }
        });

        //remove(Object,Object):boolean
        // 根据key删除key并返回key对应的v
        Integer c = map.remove("c");
        System.out.println(c);//13
        boolean c2=map.remove("c+++",13);
        System.out.println(c2);//false 应该是10
        System.out.println(map);//{java=12, c+++=10, php=18}


        //replace(key,新v):根据key设置新v，返回旧v
        Integer c3 =map.replace("c+++",15);
        System.out.println(c3);//10
        System.out.println(map);//{java=12, c+++=15, php=18}

        //*****map.entrySet*****返回所有键及所有值组成的集合Set
        Set<Map.Entry<String, Integer>> entries = map.entrySet();
        //可以使用增强for循环取遍历打印Set的内容
        //类似for(int i:arr){}
        for (Map.Entry<String,Integer>entry:entries) {
            System.out.println(entry);//输出该对象
            System.out.println(entry.getKey());//输出
            System.out.println(entry.getValue());//
        }

HasMap底层存储原理

概念图

 文字说明

0.put方法会初始化位桶Node数组的初始大小，默认为 16
1.put方法存值时，会先计算key的hashCode方法返回的int值，根据hash算法确定当前元素key在位桶中的位置
2.如果该位置无元素，则直接放入数组中
3.如果该位置有元素，则产生了hash冲突
4.产生hash冲突后，根据key的equals方法判断key是否相等，如果相等，则将key所对应的value覆盖
5.如果key的equals方法不相等，则采用尾插法将元素插入链表的尾部
6.当链表长度大于等于7时，链表转为红黑树进行存储
7.当位桶Node数组大于指定容量（指结合负载因子所计算出来的容量）时，进行扩容
8.扩容为原容量的2倍

- 建议为每个实体类都增加hashCode方法和equals方法

hashCode方法是Object类中定义的。

一般要求使用IDEA重写每个实体类的hashCode方法，保持两个对象equals比较结果和hashCode

方法返回值一致性。

@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Person)) return false;
Person person = (Person) o;
if (Double.compare(person.getSalary(), getSalary()) != 0) return false;
if (getName() != null ? !getName().equals(person.getName()) :
person.getName() != null) return false;
return getAge() != null ? getAge().equals(person.getAge()) :
person.getAge() == null;
}
@Override
public int hashCode() {
int result;
long temp;
result = getName() != null ? getName().hashCode() : 0;
result = 31 * result + (getAge() != null ? getAge().hashCode() : 0);
temp = Double.doubleToLongBits(getSalary());
result = 31 * result + (int) (temp ^ (temp >>> 32));
return result;
}

Hash冲突：两个不一 对象，hashCode的返回值结果一致。

HashMap优化

容量(Capacity): 初始容量为 16

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

最大容量  2^30

static final int MAXIMUM_CAPACITY = 1 << 30;

元素个数

size()

默认加载因子：

size/capacity的结果值， 如果大于0.75，则重新散列(rehashing)

static final float DEFAULT_LOAD_FACTOR = 0.75f;

优化：

加载因子较小时，查找性能会提高，但是会浪费桶容量

0.75是相对平衡状态

因此通过构造方法指定合理的容量，减少重新散列，提高性能。