`

【Java核心-基础】哈希表 Map

    博客分类:
  • Java
 
阅读更多



 

HashMap

这是最常使用的哈希表实现。

非线程安全

在理想情况下,如果哈希散列正常,put 和 get 等操作可达到常数时间的性能。

HashMap 使用了 链地址法 来解决哈希冲突;当冲突元素较多时又会用 树结构 替代单链表,来存储数据,以提高存取效率。

(《哈希表解决哈希冲突的方法》)

 

Hashtable

这是早期Java类库提供的一个哈希表实现。行为与 HashMap 大致相同。

线程安全;不支持 null 键和值

因为同步性能开销,不推荐使用。在需要线程安全的场景中可以使用性能更好的 ConcurrentHashMap。

 

TreeMap

这是基于红黑树的 Map,支持按照 key 的排序顺序遍历数据(可通过构造方法指定 key 的 Comparator)

它的 get、put、remove 等操作时间复杂度都是 O(long(n))。

 

LinkedHashMap

继承自 HashMap,支持按照键值对的“访问”顺序遍历数据,最不常被访问的键值对排在最前
内部有一个双向链表来记录键值对的插入顺序。
put、get、compute等相关操作都属于访问。默认情况下,读取(get、getOrDefault)不会对内部链表顺序产生影响;可以通过构造方法指定

 

示例:利用 LinkedHashMap 实现对空间占用敏感的缓存

LinkedHashMap<String, String> accessOrderedMap = new LinkedHashMap<String, String>(16, 0.75F, true){
  @Override
  protected boolean removeEldestEntry(Entry<String, String> eldest) {
    // 缓存最多只能存 3 个键值对
    return size() > 3;
  }
};

// 添加数据
accessOrderedMap.put("key1", "v1");
accessOrderedMap.put("key2", "v2");
accessOrderedMap.put("key3", "v3");
// 遍历数据。输出顺序应是:key1、key2、key3
accessOrderedMap.forEach((k,v) -> System.out.println(k + ":" + v));

// 读取数据
accessOrderedMap.get("key1");
accessOrderedMap.get("key3");
// 遍历数据。输出顺序应是:key2, key1, key3
accessOrderedMap.forEach((k,v) -> System.out.println(k + ":" + v));

// 添加数据
accessOrderedMap.put("key4", "v4);
// 遍历数据。输出顺序应是:key1, key3, key4。因为超过缓存上限 3,key2 被移除了
accessOrderedMap.forEach((k,v) -> System.out.println(k + ":" + v));
  • 大小: 81 KB
分享到:
评论

相关推荐

    算法面试通关40讲完整课件 14-17 哈希表(HashTable)

    哈希表(HashTable)是计算机科学中一种非常重要的...熟悉不同编程语言中的哈希表实现,如Python的dict、C++的unordered_map和Java的HashMap,以及在面对冲突时如何有效地管理这些数据结构,将有助于在面试中脱颖而出。

    Hash map 哈希表

    哈希表,也被称为Hash Map,是计算机科学中一种高效的数据结构,用于存储键值对。它通过一种称为哈希函数的过程将键映射到数组的特定位置,从而实现快速的查找、插入和删除操作。在哈希表中,查找时间通常接近常数...

    哈希表-浙大数据结构课件

    4. 常见的哈希表实现:在实际编程中,C++中的`std::unordered_map`、Java中的`HashMap`以及Python的`dict`都是基于哈希表实现的高效容器。这些数据结构提供了高效的插入、删除和查找操作,广泛应用于软件开发的各个...

    哈希表实现简单说明-附代码

    哈希表是一种高效的数据结构,它通过特定的哈希函数将键...例如,Python中的`dict`类型、Java的`HashMap`和C++的`std::unordered_map`都是哈希表的典型实现。理解哈希表的工作原理和优化策略对于提升程序性能至关重要。

    Java-list-set-map.zip_Java list

    在Java编程语言中,集合框架是处理对象组的重要工具,其中`List`、`Set`和`Map`是三大核心接口。本资料“Java list set map.zip”专注于讲解这些接口及其相关实现,帮助开发者深入理解Java集合类的使用。 首先,`...

    数据结构 哈希表 哈希算法

    哈希表的核心在于哈希函数。哈希函数的作用是将关键字(通常为字符串)转换为数组的索引,以便在数组中存储或查找对应的元素。一个好的哈希函数应该具备以下特点: 1. **均匀性**:哈希函数应尽可能使得不同的关键字...

    哈希表的设计与实现.rar

    例如,Java中的`HashMap`和C++中的`unordered_map`都是内置的哈希表实现。 6. **文档解读**:课程设计可能包括详细的理论介绍和步骤指南,涵盖了哈希表的基本概念、算法流程、性能分析等内容。通过阅读文档,我们...

    java-leetcode面试题解哈希表第1371题每个元音包含偶数次的最长子字符串-题解.zip

    在准备Java面试,特别是涉及到LeetCode挑战和哈希表技巧的时候,这道第1371题是一个重要的知识点。题目要求找到一个字符串中最长的子串,其中所有的元音字母(a, e, i, o, u)出现次数都是偶数。这个题目考察的是...

    达内java课程-java核心编程10天

    ### 达内Java课程——Java核心编程10天知识点详解 #### 散列表Map - **概念**: 散列表是一种非常高效的数据结构,它通过特定的哈希函数将键值映射到表的一个位置来访问记录,这使得查找操作能在平均时间复杂度为O(1...

    Java基础----集合类汇总

    本文将深入探讨Java集合类的汇总,包括List、Set和Map这三大核心接口及其实现类。 首先,让我们从List接口开始。List是一种有序的集合,允许有重复元素,并且支持通过索引来访问元素。ArrayList和LinkedList是List...

    JAVA哈希表.pdf

    在Java中,`java.util.Hashtable`类是实现哈希表的一种方式,它继承自`Dictionary`类并实现了`Map`接口。 哈希表的主要优点在于查找、插入和删除操作的速度,尤其是在处理大量数据时。`Hashtable`类提供了几个构造...

    java笔记--集合类

    `HashMap`是`Map`接口的实现,使用哈希表存储键值对,通过计算键的哈希值来定位数据,从而实现高效的查找、插入和删除操作。 - **哈希函数的作用**:哈希函数是`HashMap`实现高效查找的关键。它将任意长度的键转换...

    Java基础-个人总结-超详细清楚-用于面试-针对无基础或有基础回忆.docx

    Java基础是编程学习的核心部分,本总结主要涵盖了Java语言的基础概念和常见问题,适用于初学者和需要回顾基础知识的开发者。以下是对这些知识点的详细解释: 1. **基本数据类型**: - Java提供了八种基本数据类型...

    【IT十八掌徐培成】Java基础第11天-02.Map集合-hash原理.zip

    HashMap是Java中最常用的Map实现,它基于哈希表(散列表)实现,提供了近乎常数时间的插入、删除和查找操作。哈希表的工作原理是通过键的哈希函数将键转换为一个哈希码,然后根据这个哈希码将键值对存储在数组中。...

    【IT十八掌徐培成】Java基础第11天-03.Map集合-hash原理2.zip

    在本课程“【IT十八掌徐培成】Java基础第11天-03.Map集合-hash原理2”中,我们将深入探讨Map集合的内部机制,特别是哈希(Hash)原理的应用。这个课程的视频文件名为“Java基础第11天-03.Map集合-hash原理2.avi”。 ...

    Java 基础核心总结-副本

    Set接口不允许重复元素,HashSet和TreeSet分别基于哈希表和红黑树实现。 五、多线程 Java支持多线程编程,可以同时执行多个任务。Thread类是线程的基类,Runnable接口也可用于创建线程。线程同步是解决并发问题的...

    Java--collection.rar_SEP_java 集合

    Java集合框架是Java编程语言中的一个核心组件,它为数据存储和管理提供了强大的支持。这个框架包括了多种接口和类,使得程序员可以高效地处理对象集合。在"Java--collection.rar"这个压缩包中,我们可以找到名为...

    java面试-leetcode面试java编程题解之第3题无重复字符的最长子串-java题解.zip

    总之,理解和熟练掌握如何用Java解决LeetCode第3题“无重复字符的最长子串”不仅能提升你在求职面试中的竞争力,还能强化对字符串处理、哈希表以及滑动窗口等编程技巧的理解。通过不断地练习和优化,你将能够在面对...

    应聘Java--笔试常出现的问题

    - `HashMap`:基于哈希表实现的`Map`。 - `TreeMap`:基于红黑树实现的`Map`,提供排序功能。 - **自定义数据结构**: - 要自定义一个数据结构,首先需要确定该数据结构的需求,比如是否需要支持快速查找、是否...

    java-collections-framework1016

    - **`LinkedHashMap`**:基于哈希表和链表实现的`Map`接口,保持元素的插入顺序。 - **`TreeMap`**:基于红黑树实现的`Map`接口,可按键的自然顺序或指定比较器排序。 **历史集合类:** Java早期版本中存在一些...

Global site tag (gtag.js) - Google Analytics