哈希表相关知识
目录
哈希表(Hash Table),也叫散列表,是一种根据关键码值(Key value)而直接进行访问的数据结构。
一、基本原理
1. 哈希函数:
• 哈希表通过一个特定的哈希函数,将关键码映射到表中的一个位置。这个位置被称为哈希地址或哈希值。
• 例如,一个简单的哈希函数可以是取关键码的模运算,如对于关键码为整数的情况,哈希函数hash(key) = key % table_size,其中table_size是哈希表的大小。
2. 冲突解决:
• 由于不同的关键码可能会映射到相同的哈希地址,这就会产生冲突。解决冲突的方法有多种,常见的有开放寻址法和链地址法。
• 开放寻址法是当发生冲突时,通过探测哈希表中的其他位置来寻找空闲位置存放元素。例如线性探测,当发生冲突时,依次检查下一个位置,直到找到空闲位置。
• 链地址法是在每个哈希地址处维护一个链表,所有映射到该地址的元素都存储在这个链表中。
二、特点与优势
1. 快速查找:
• 哈希表的查找操作非常高效,平均时间复杂度可以接近 O(1)。只要给定关键码,通过哈希函数计算出哈希地址,就可以直接访问相应的位置。
• 这使得哈希表在需要快速查找、插入和删除操作的场景中非常有用,比如数据库索引、缓存系统等。
2. 灵活性:
• 哈希表可以存储不同类型的关键码和值,只要能够为这些关键码定义合适的哈希函数。
• 它可以适应动态变化的数据集合,能够方便地进行插入和删除操作。
三、应用场景
1. 数据库索引:
• 在数据库系统中,哈希表可以用于构建索引,加快数据的查找速度。例如,对于一个存储学生信息的数据库表,可以根据学生的学号作为关键码,通过哈希函数将学号映射到哈希表中的位置,快速定位到相应的学生记录。
2. 缓存系统:
• 缓存系统通常使用哈希表来存储最近访问的数据项,以便快速响应后续的请求。当需要访问一个数据项时,首先在缓存中查找,如果找到则直接返回,否则从数据源获取并放入缓存中。
3. 编程语言中的数据结构实现:
• 许多编程语言的内部实现中都使用了哈希表,例如 C++的std::unordered_map和std::unordered_set、Java 的HashMap和HashSet等。这些数据结构提供了高效的键值对存储和查找功能,方便程序员在开发中使用。
在 Java 中,有多种与哈希相关的数据结构。
一、HashMap
1. 基本概念:
• HashMap是 Java 中常用的一种基于哈希表实现的键值对存储结构。它允许存储键值对<K, V>,其中键K必须是唯一的,通过键可以快速地查找对应的值V。
• 例如:HashMap<String, Integer> map = new HashMap<>(); 创建了一个键为String类型、值为Integer类型的HashMap。
2. 工作原理:
• HashMap使用哈希函数将键映射到内部数组的索引位置。当插入一个键值对时,首先计算键的哈希值,然后根据哈希值确定在内部数组中的存储位置。
• 如果多个键的哈希值相同,就会发生冲突。HashMap通过链地址法解决冲突,即在每个索引位置上维护一个链表或红黑树(当链表长度超过一定阈值时会转换为红黑树),存储具有相同哈希值的键值对。
3. 特点与优势:
• 快速查找和插入:平均情况下,查找、插入和删除操作的时间复杂度为 O(1)。
• 允许键值为空:HashMap允许键和值为null,但只能有一个键为null,可以有多个值为null。
• 动态调整大小:随着存储的键值对数量增加,HashMap会自动调整内部数组的大小,以保持高效的性能。
一、HashMap 常用方法:
1. put(K key, V value):将指定的键值对添加到映射中。
• 例如:map.put("apple", 5); 将键为“apple”,值为 5 的键值对放入 HashMap 中。
2. get(Object key):返回指定键所映射的值。
• 例如:int value = map.get("apple"); 获取键为“apple”的值。
3. remove(Object key):从映射中移除指定键的键值对。
• 例如:map.remove("apple"); 移除键为“apple”的键值对。
4. size():返回映射中的键值对数量。
• 例如:int size = map.size(); 获取 HashMap 的大小。
5. containsKey(Object key):判断映射中是否包含指定的键。
• 例如:boolean hasKey = map.containsKey("apple"); 判断是否存在键为“apple”的键值对。
二、HashSet
1. 基本概念:
• HashSet是一种集合数据结构,它基于哈希表实现,不允许存储重复的元素。
• 例如:HashSet<String> set = new HashSet<>(); 创建了一个存储String类型元素的HashSet。
2. 工作原理:
• HashSet内部使用HashMap来存储元素,将元素作为键,而值则是一个固定的占位对象(如Object类型的常量)。
• 当向HashSet中添加元素时,实际上是将元素作为键添加到内部的HashMap中。由于HashMap不允许重复的键,所以HashSet也能保证不存储重复元素。
3. 特点与优势:
• 快速查找和添加:与HashMap类似,具有快速的查找和添加操作性能。
• 不允许重复元素:确保集合中每个元素都是唯一的,适合需要去重的场景。
二、HashSet 常用方法:
1. add(E e):将指定的元素添加到集合中。
• 例如:set.add("apple"); 将“apple”添加到 HashSet 中。
2. remove(Object o):从集合中移除指定的元素。
• 例如:set.remove("apple"); 移除“apple”元素。
3. size():返回集合中的元素数量。
• 例如:int size = set.size(); 获取 HashSet 的大小。
4. contains(Object o):判断集合中是否包含指定的元素。
• 例如:boolean hasElement = set.contains("apple"); 判断是否存在“apple”元素。
三、哈希在 Java 中的重要性
1. 提高性能:
• 在处理大量数据时,哈希结构能够快速地进行查找、插入和删除操作,大大提高了程序的性能。例如,在处理用户信息管理系统中,使用HashMap存储用户 ID 和用户对象的映射,可以快速根据用户 ID 查找用户信息。
2. 方便的数据管理:
• 哈希结构提供了一种方便的方式来管理和组织数据。通过键值对的形式,可以根据特定的键快速访问对应的值,使得数据的存储和检索更加高效和灵活。
• 例如,在一个电商系统中,可以使用HashMap存储商品的 SKU(库存单位)和商品信息的映射,方便根据 SKU 查找商品的详细信息。
在 Java 中,哈希结构通常使用 HashMap、HashSet 等集合类实现。以下是一些常用方法:
在 C++ 中,有多种与哈希相关的数据结构。
集合
集合 | 底层实现 | 是否有序 | 数值是否可以重复 | 能否更改数值 | 查询效率 | 增删效率 |
---|---|---|---|---|---|---|
std::set | 红黑树 | 有序 | 否 | 否 | O(log n) | O(log n) |
std::multiset | 红黑树 | 有序 | 是 | 否 | O(logn) | O(logn) |
std::unordered_set | 哈希表 | 无序 | 否 | 否 | O(1) | O(1) |
std::unordered_set底层实现为哈希表。
std::set 和std::multiset 的底层实现是红黑树,红黑树是一种平衡二叉搜索树,所以key值是有序的,但key不可以修改,改动key值会导致整棵树的错乱,所以只能删除和增加。
映射
映射 | 底层实现 | 是否有序 | 数值是否可以重复 | 能否更改数值 | 查询效率 | 增删效率 |
---|---|---|---|---|---|---|
std::map | 红黑树 | key有序 | 否 | 否 | O(logn) | O(logn) |
std::multimap | 红黑树 | key有序 | 是 | 否 | O(log n) | O(log n) |
std::unordered_map | 哈希表 | key无序 | 否 | 否 | O(1) | O(1) |
std::unordered_map 底层实现为哈希表。
std::map 和std::multimap 的底层实现是红黑树。同理,std::map 和std::multimap 的key也是有序的。
用法
当我们要使用集合来解决哈希问题的时候,优先使用unordered_set,因为它的查询和增删效率是最优的,如果需要集合是有序的,那么就用set,如果要求不仅有序还要有重复数据的话,那么就用multiset。
在map 是一个key value 的数据结构,map中,对key是有限制,对value没有限制的,因为key的存储方式使用红黑树实现的。
哈希表使用场景
快速判断一个元素是否出现集合里时,考虑哈希法。
哈希法是牺牲了空间换取了时间,才能实现快速的查找。
原文地址:https://blog.csdn.net/2301_81718046/article/details/142535113
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!