04.数据结构—哈希表与字符串

数据结构—哈希表与字符串

相关数据结构实现用go语言实现

相关代码做题合集：https://github.com/longpi1/algorithm-pattern

一、什么是哈希表？（Hash Table / Hash Map / Dictionary）

哈希表是一种实现关联数组（associative array）抽象数据类型的数据结构。它能够将键（Key）映射到值（Value），提供平均O(1)的查找、插入和删除时间复杂度。

核心思想：

1. 哈希函数（Hash Function）： 将任意大小的键（例如一个字符串）转换成一个固定大小的整数（哈希值或哈希码）。这个哈希值通常被用来作为数组的索引。

2. 数组（Buckets / Slots）： 哈希值会指向哈希表内部的一个“桶”或“槽”。

3. 冲突解决（Collision Resolution）：

   不同的键可能通过哈希函数得到相同的哈希值，这就是哈希冲突。常见的解决办法有：

   • 链地址法（Chaining）： 每个桶存储一个链表，所有哈希到该桶的键值对都添加到链表中。
   • 开放寻址法（Open Addressing）： 当发生冲突时，在数组中寻找下一个可用的空位。

哈希表的效率高度依赖于哈希函数的质量，一个好的哈希函数应该能够均匀地分布键的哈希值，从而减少冲突。

在理想情况下（哈希函数均匀分布且冲突较少），哈希表的操作时间复杂度为：

• 插入：O(1)
• 查找：O(1)
• 删除：O(1)

但在最坏情况下（例如大量冲突导致链表过长或探测次数过多），时间复杂度可能退化为 O(n)，其中 n 为哈希表中元素的数量。

go如何实现map源码分析可参考：Golang Map源码分析

二、什么是字符串？

字符串是字符的序列。在多数编程语言中，字符串是不可变的（immutable），这意味着一旦创建，它的内容就不能被改变。每次对字符串进行修改操作（如拼接），都会创建一个新的字符串。这种特性对于哈希表作为键来说非常重要，因为它保证了字符串的哈希值在整个生命周期中是稳定的。

三、算法示例

242. 有效的字母异位词

/*
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。



示例 1:

输入: s = "anagram", t = "nagaram"
输出: true
示例 2:

输入: s = "rat", t = "car"
输出: false


提示:

1 <= s.length, t.length <= 5 * 104
s 和 t 仅包含小写字母


进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
*/

func isAnagram(s, t string) bool {
	if len(s) != len(t) {
		return false
	}
	cnt := map[rune]int{}
	for _, ch := range s {
		cnt[ch]++
	}
	for _, ch := range t {
		cnt[ch]--
		if cnt[ch] < 0 {
			return false
		}
	}
	return true
}

344. 反转字符串

/*
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。



示例 1：

输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]
示例 2：

输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]


提示：

1 <= s.length <= 105
s[i] 都是 ASCII 码表中的可打印字符
*/

func reverseString(s []byte) {
	right := len(s) - 1
	left := 0
	for left < right {
		tmp := s[left]
		s[left] = s[right]
		s[right] = tmp
		left++
		right--
	}

}