蔡不菜和他的uU们

  • 首页
  • 新鲜出炉
  • 我的记录
  • 我的动态
  • 我和uU
  • 好用分享
  • 关于与留言
志合者,不以山海为远;道乖者,不以咫尺为近
  1. 首页
  2. 学习,学习
  3. 正文

JavaSE — Map

2022年7月16日 483人阅读 0人点赞 0条评论

1 HashMap

1.1 底层实现

1.1.1 哈希表是一个怎样的数据结构

数组+单向链表的结合体
数组:在查询方面效率很高,随机增删效率很低
单向链表:在随机增删方面效率很高,在查询方面效率很低
哈希表将以上的两种数据结构融合在一起,充分发挥它们各自的优点

1.1.2 为什么哈希表的增删,以及查询效率都很高

增删是在链表上完成的

查询也不需要都扫描,只要部分扫描,
key 会先后调用hashCode() 方法,equals方法

1.1.3 哈希表使用不当会出现的问题

哈希表使用不当时,无法发挥性能

假设将所有的hashcode返回的是一个固定值,那么会导致哈希表变成了纯单向链表,这种情况我们称为,散列分布不均匀
假设将所有的hashcode返回的是不一样的值,会导致底层哈希表变成一维数组,没有链表的概念了,也是散列分布不均匀的
散列分布均匀的,需要在重写hashcode方法时注意一定的技巧

1.2 特性

默认初始容量 16

hashmap集合初始化容量必须是2的倍数,官方推荐的,这是为了达到散列均匀,提高存取效率

扩容:默认加载因子为 0.75,达到75% 开始扩容为原来的两倍

加载因子 0.75

key部分的特点 无序,不可重复

为什么无序,不可重复是怎么保证的,

equals方法来保证hashmap的key是不可重复的,如果重复了,value会被覆盖

HashMap 在JDK8 之后 如果在单向链表上存储的元素超过 8个,单向链表会变成红黑树,当红黑树上元素少于6个,又会变为链表

hashMap 集合允许key和value为null,但是hashMap 的null 值只能有一个

1.3 源码

public class HashMap(){

Node<K,V> [] table;
// 静态内部类

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash; // 哈希值,是key的hashcode方法的执行结果 hash值可以通过hash函数,转换为数组下标
    final K key; // 存储到Map集合中的那个key
    V value; // 存储到Map集合中的那个value
    Node<K,V> next; // 下一个节点的内存地址

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}   
}

1.4 常用方法

remove(Object key) 移除指定键值对

replace(K key,V oldValue, V newValue) 更新键值对

1.5 HashMap的存取

1.5.1 map.put(K k,V v)

第一步:先将KV 封装成 Node 对象

第二步:底层调用hashcode()方法得到hash值,然后通过哈希函数(哈希算法)将hash值转换为数组下标,下标位置上没有任何元素,就把node添加到这个位置,如果说下标对应的位置上有链表,此时会拿着key和链表上每一个节点进行equals,如果所有的equals方法返回都是false,那么这个新节点就会被添加到链表的末尾,如果其中一个equals返回了true,会把新节点的value进行替换,原来的value被覆盖

1.5.2 map.get(k)

先调用hashCode() 方法得到hashcode,通过hash函数,转换成数组下标,通过数组下标快速定位到某个位置上,如果这个位置上什么也没有,返回null,如果这个位置上有单向链表,那么会拿着key 和单向链表上的每个节点上的k进行equals ,如果所有的equals方法返回false,那么get方法返回null,只要其中有一个节点的k和参数k equals的时候返回true,那么此时这个节点的value就是我们要找的value,get方法返回这个要找的value

1.5.3 Map 存取

都是先调用hashCode() 然后调用 equals()

equals方法,有可能调用,也有可能不调用
不调用的情况,hashcode转换为数组下标 ,该位置没有元素,返回null,此时不会调用

1.6 HashMap的遍历

  1. 先使用keySet() 获取key集合,然后遍历key集合 获取 get(key) 

    Set<Integer> set = map.keySet();
    
    for(Integer key:set){
          System.out.println(key+"="+map.get(key));
    }
  2. 使用entrySet()转换为set,然后再对set进行遍历 效率较高(大数据量)

    Set> set = map.entrySet();
    
    for (Map.Entry item : set) {
         System.out.println(item);
    }
    
    Set> set = map.entrySet();
    
    Iterator> it = entrySet.iterator();
    
    while(it.hasNext()){
        System.out.println(it.next());
    }

1.7 重要

hashcode方法和equals方法,可以直接使用IDEA工具生成,但是这两个方法需要同时生成

hashMap 集合允许key和value为null,但是hashMap 的null 值只能有一个

HashMap 在JDK8 之后 如果在单向链表上存储的元素超过 8个,单向链表会变成红黑树,当红黑树上元素少于6个,又会变为链表

2 Hashtable

2.1 特性

Hashtable 不支持key为null,也不支持value为null,否则会报java.lang.NullPointerException

Hashtable 是线程安全的,方法都有synchronized修饰,但是效率较低,有新的解决方案

hashtable 初始化容量是11,默认加载因子 0.75 扩容到原来的两倍+1

3 Properties

3.1 特点

属性类对象 继承Hashtable

线程安全

properties的key和value只能是string

3.2 常用方法

setProperty(K k,V v)  // 添加属性,底层是调用的map.put() 方法

getProperty(K k)

4 SortedMap接口

4.1 特点

SortedMap接口的存储元素的特点
由于继承了set接口,所以他的特点也是无序不可重复的,
但是放在SortedSet接口中的元素可以自动排序,
放到该集合中的元素是自动按照大小顺序进行排序的

5 TreeMap

5.1 特点

TreeMap集合采用的是,中序遍历方式

TreeMap集合key部分的时候,需要进行排序,实现方式有两种

  1. 放到集合中的元素实现java.lang.Comparable 接口

  2. 在构造TreeSet 或者 TreeMap 集合的时候给它传一个比较器对象,(匿名内部类的形式,或者新建一个比较器class传入)

5.2 底层数据结构 二叉树

6 重要注意事项

存放在集合中的元素类型,需要重写equals方法

Map和Collection 没有继承关系

TreeSet集合,TreeMap集合采用的是,中序遍历方式

放到TreeSet或TreeMap集合key部分的时候,需要进行排序,实现方式有两种

  1. 放到集合中的元素实现java.lang.Comparable 接口 在compareTo方法写排序规则
  2. 在构造TreeSet 或者 TreeMap 集合的时候给它传一个比较器对象,(匿名内部类的形式,或者新建一个比较器class传入)

6.1 Comparable 和 Comparator 怎么选择 ?

比较规则不轻易改变 选择实现Comparable 接口,(例如 Integer,String,Date,)
比较规则有多种,并且需要进行切换,实现Comparator 接口

对set集合进行排序,需要先转换为list,然后再用Collections.sort()

构造方法中传入比较器对象,写比较规则

TreeSet ts  =new TreeSet<>(new Comparator() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2 - o1;
    }
});

remove contain compareTo 方法底层调用的是equals方法

6.2 使用泛型

1.JDK 5.0 之后推出的新特性:泛型

2.泛型属于编译器阶段的新特性,只是给编译器参考的,运行阶段泛型没用

6.2.1 优点

保证了集合中元素的统一性

从集合中取出的元素类型是泛型指定类型,不需要进行大量的向下转型

6.2.2 缺点

导致集合中存储的元素缺乏多样性

大多数业务中,集合中元素类型还是统一的,所以还是能被接受的

6.2.3 自定义泛型

6.2.4 其他

JDK 8 之后引入了自动类型推断机制(又称为砖石表达式)

迭代时也需要指定迭代的泛型

7 Collections工具类

7.1 常用方法

Collections.synchronizedList(list) 将线程不安全的ArrayList 转换为线程安全的

Collections.sort(wu); 进行排序的list 存取的元素类型需要实现 comparable 接口

Collections.sort(myList 待排序数组, Comparator 比较器对象);

对set集合进行排序,需要先转换为list,然后再用Collections.sort()

7.2 集合之间转换

7.2.1 set和list之间的转换

// HashSet转换为ArrayList

HashSet set = new HashSet();

ArrayList list = new ArrayList(set);

// 使用构造方法即可完成转换

7.2.2 map和set之间的转换

Set set = map.entrySet()

7.2.3 其他转换 使用构造方法

标签: JavaSE 算法与数据结构;
最后更新:2022年7月16日

Csy

这个人很懒,什么都没留下

点赞
< 上一篇
下一篇 >

文章评论

取消回复
文章目录
  • 1 HashMap
    • 1.1 底层实现
    • 1.2 特性
    • 1.3 源码
    • 1.4 常用方法
    • 1.5 HashMap的存取
    • 1.6 HashMap的遍历
    • 1.7 重要
  • 2 Hashtable
    • 2.1 特性
  • 3 Properties
    • 3.1 特点
    • 3.2 常用方法
  • 4 SortedMap接口
    • 4.1 特点
  • 5 TreeMap
    • 5.1 特点
    • 5.2 底层数据结构 二叉树
  • 6 重要注意事项
    • 6.1 Comparable 和 Comparator 怎么选择 ?
    • 6.2 使用泛型
  • 7 Collections工具类
    • 7.1 常用方法
    • 7.2 集合之间转换

COPYRIGHT © 2021 caibucai.top. ALL RIGHTS RESERVED.

THEME KRATOS MADE BY VTROIS

豫ICP备2021018055号