数据结构之Map/Set讲解+硬核源码剖析(二)

简介: 数据结构之Map/Set讲解+硬核源码剖析(二)

数据结构之Map/Set讲解+硬核源码剖析(一)+https://developer.aliyun.com/article/1413569

get和getOrDefault的源码
// get也可以用来判断是否包含相应的key
        public V get(Object key) {
            TreeMap.Entry<K,V> p = getEntry(key);
            return (p==null ? null : p.value);
        }
        default V getOrDefault(Object key, V defaultValue) {
            V v;  // 三目运算符   为真返回v  为假返回默认值
            return (((v = get(key)) != null) || containsKey(key))
                    ? v
                    : defaultValue;
        }

3.remove

 删除key对应的映射关系

源码:注意remove存在返回值

// remove存在返回值!!!  返回你要删除的key对应的value
        public V remove(Object key) {
            TreeMap.Entry<K,V> p = getEntry(key);
            if (p == null)
                return null;
            V oldValue = p.value;
            deleteEntry(p);
            return oldValue;
        }

验证

System.out.println(map.remove("cat"));// 输出17
        System.out.println(map.remove("Dog"));// 输出null

4.contains  

包含两个contains方法,一个是判断是否存在key,一个判断是否存在value

System.out.println(map.containsKey("cat"));// 输出true
        System.out.println(map.containsKey("Dog"));// 输出false
        System.out.println(map.containsValue(15));// 输出true
        System.out.println(map.containsValue(100));// 输出false

源码

public boolean containsKey(Object key) {
        return getEntry(key) != null;
    }
    public boolean containsValue(Object value) {
        for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
            if (valEquals(value, e.value))
                return true;
        return false;
    }

5.keySet方法

  返回不重复的key的集合  就是将Map中所有的key值存放到Set内部(存的时候会进行排序)

// 此处Set里面存放的类型要和key一致!!!
        Set<String> set = map.keySet();
        for (String s:set) {
            System.out.print(s + " ");// 输出apple bank cat
        }

源码

public Set<K> keySet() {
        return navigableKeySet();
    }
    /**
     * @since 1.6
     */
    public NavigableSet<K> navigableKeySet() {
        KeySet<K> nks = navigableKeySet;
        return (nks != null) ? nks : (navigableKeySet = new KeySet<>(this));
    }

6.values

 返回所有的value的可重复集合  和上一个方法类似  此方法是拿到所有的value将其存放到Collection里面

Collection<Integer> collection = map.values();
        for (int val:collection) {
            System.out.print(val + " ");// 输出14 15 17 
        }

源码

public Collection<V> values() {
        Collection<V> vs = values;
        if (vs == null) {
            vs = new Values();
            values = vs;
        }
        return vs;
    }

7.entrySet方法

返回所有的key--value的映射关系  可以理解为keySet和values的集合版本

Set<Map.Entry<String,Integer>> set = map.entrySet();
        for (Map.Entry<String,Integer> entry:set) {
            System.out.println("key = " + entry.getKey() + " " +"value = " + entry.getValue());
        }
        // 也可以直接打印
        System.out.println(set); // 输出[apple=14, bank=15, cat=17]

注意:getKey和getValue是Map的内部类Entry中的方法  用于返回映射中的key和value,所以entrySet方法就相当于创建的Set集合中存储是一个一个Entry

注意:

1.Map是一个接口,只能实例化实现他的类,如TreeMap和HashMap,区别在于前者的底层是二叉搜索树,后者的底层是哈希表

2.Map中存放的key是唯一的(二叉搜索树中不能存放相同的值,哈希表中也不能存放相同的值)

3.在TreeMap中插入键值对时,key不能为空,否则就会抛NullPointerException异常,因为每次put一个元素都需要进行一次比较,而null不能直接比较,value可以为空。但 是HashMap的key和value都可以为空

4.利用keySet方法可以将所有的key分离出来(存放到set里),利用values方法可以将所有的value分离出来(存放到Collection内部)

5.Map中的key不能直接修改,value可以修改(会直接被替换为新值,在二叉搜索树的put代码中就有)

四.set的使用

1.概念

 Set是一种纯key模型的数据集合容器 Set是继承自Collection的接口类,也就是Set中不存在values

2.常用方法

3.注意事项:

1.TreeSet的底层其实是TreeMap,所以TreeSet无法存放相同的key值

2.Set实现了toString方法,可以直接打印

Set<String> set = new TreeSet<>();
        set.add("lvzi");
        set.add("biandu");
        set.add("zhizi");
        System.out.println(set);// 输出[biandu, lvzi, zhizi]

3.Set最大的功能就是对集合中的元素进行去重

4.实现Set接口的常用类有TreeSet和HashSet,还有一个LinkedHashSet,LinkedHashSet是在HashSet的基础 上维护了一个双向链表来记录元素的插入次序。

5.TreeSet中不能插入null的key,HashSet可以

五.哈希表

1.概念

1.什么是哈希表

 在顺序结构和平衡二叉树的存储结构中,如果想要搜索某个元素,必须要进行关键码(key)的多次比较,顺序结构的搜索效率是O(N),平衡二叉树的搜索效率是O(logN),搜索的效率取决于比较的次数,,其实之所以需要比较是因为关键码(key)和值(val)之间没有一一对应的关系,如果建立一种关键码与存储位置一一对应的映射,那么我们就能不进行比较就拿到我们需要的数据。比如,,对于一个正比例函数,x与y之间是一一对应的,可以说y与x建立了一一对应的映射关系。

 在计算机中,也有这样的一种数据结构,叫做哈希表,实现了关键码和存储位置的一一映射

这种映射关系通过哈希函数(hashFunc)建立(就像正比例函数建立x与y的映射关系一样)

比如:哈希函数设置为:hash(key) = key % capacity; capacity为存储元素底层空间总的大小。

2.哈希冲突

 如上图,如果我们再存储一个14,14%10 = 4,他的索引应该是4,但是4下标对应关键字key,不能再对应14了,此时就发生了哈希冲突

3.负载因子

α = 填入表中的元素 / 哈希表的长度

负载因子α用于定性描述冲突率,研究表明,负载因子越大,发生哈希冲突的概率就越大;负载因子越小,发生哈希冲突的概率就越小

2.常见的哈希函数

1.直接定制法

 利用关键字的特性建立线性函数,实现关键字和存储位置的一一对应!

适用于数据简单,连续的情况

相关面试题:

387. 字符串中的第一个唯一字符 - 力扣(LeetCode)

思路分析

代码实现

// 1.使用计数数组
class Solution {
    public int firstUniqChar(String s) {
        int[] cnt = new int[26];
        for (int i = 0; i < s.length(); i++) {
            cnt[s.charAt(i) - 'a']++;
        }
        for (int i = 0; i < s.length(); i++) {
            if(cnt[s.charAt(i) - 'a'] == 1) {
                return i;
            }
        }
        return -1;
    }
}
        2.// 使用哈希表
        Map<Character,Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            // 先获取ch的val  无论是否存在  是要val+1  不存在 设置默认值为0 更新后变为1
            map.put(ch,map.getOrDefault(ch,0)+1);
        }
        for (int i = 0; i < s.length(); i++) {
            if(map.get(s.charAt(i)) == 1) {
                return i;
            }
        }
        return -1;

数据结构之Map/Set讲解+硬核源码剖析(三)+https://developer.aliyun.com/article/1413573


目录
相关文章
|
9天前
|
存储 Java
告别混乱!用Java Map优雅管理你的数据结构
【10月更文挑战第17天】在软件开发中,随着项目复杂度增加,数据结构的组织和管理至关重要。Java中的Map接口提供了一种优雅的解决方案,帮助我们高效、清晰地管理数据。本文通过在线购物平台的案例,展示了Map在商品管理、用户管理和订单管理中的具体应用,有效提升了代码质量和维护性。
37 2
|
9天前
|
存储 Java 开发者
Java Map实战:用HashMap和TreeMap轻松解决复杂数据结构问题!
【10月更文挑战第17天】本文深入探讨了Java中HashMap和TreeMap两种Map类型的特性和应用场景。HashMap基于哈希表实现,支持高效的数据操作且允许键值为null;TreeMap基于红黑树实现,支持自然排序或自定义排序,确保元素有序。文章通过具体示例展示了两者的实战应用,帮助开发者根据实际需求选择合适的数据结构,提高开发效率。
32 2
|
19天前
|
缓存 Java 程序员
Map - LinkedHashSet&Map源码解析
Map - LinkedHashSet&Map源码解析
39 0
|
19天前
|
算法 Java 容器
Map - HashSet & HashMap 源码解析
Map - HashSet & HashMap 源码解析
29 0
|
1天前
|
存储 C语言
【数据结构】顺序表(c语言实现)(附源码)
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列,常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构,其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别,并重点介绍了动态顺序表的实现,包括初始化、销毁、打印、增删查改等操作。最后,文章总结了顺序表的时间复杂度和局限性,并预告了后续关于链表的内容。
11 3
|
7天前
|
存储 Java 开发者
Java中的Map接口提供了一种优雅的方式来管理数据结构,使代码更加清晰、高效
【10月更文挑战第19天】在软件开发中,随着项目复杂度的增加,数据结构的组织和管理变得至关重要。Java中的Map接口提供了一种优雅的方式来管理数据结构,使代码更加清晰、高效。本文通过在线购物平台的案例,展示了Map在商品管理、用户管理和订单管理中的具体应用,帮助开发者告别混乱,提升代码质量。
17 1
|
17天前
|
Java C++ 索引
让星星⭐月亮告诉你,LinkedList和ArrayList底层数据结构及方法源码说明
`LinkedList` 和 `ArrayList` 是 Java 中两种常见的列表实现。`LinkedList` 基于双向链表,适合频繁的插入和删除操作,但按索引访问元素效率较低。`ArrayList` 基于动态数组,支持快速随机访问,但在中间位置插入或删除元素时性能较差。两者均实现了 `List` 接口,`LinkedList` 还额外实现了 `Deque` 接口,提供了更多队列操作。
20 3
|
19天前
|
存储 JavaScript 前端开发
Set、Map、WeakSet 和 WeakMap 的区别
在 JavaScript 中,Set 和 Map 用于存储唯一值和键值对,支持多种操作方法,如添加、删除和检查元素。WeakSet 和 WeakMap 则存储弱引用的对象,有助于防止内存泄漏,适合特定场景使用。
|
22天前
|
存储 缓存 Java
【用Java学习数据结构系列】HashMap与TreeMap的区别,以及Map与Set的关系
【用Java学习数据结构系列】HashMap与TreeMap的区别,以及Map与Set的关系
30 1
|
19天前
|
算法 Java 程序员
Map - TreeSet & TreeMap 源码解析
Map - TreeSet & TreeMap 源码解析
29 0