10.14 哈希表基础理论 242.有效的字母异位词

哈希表基础理论

1.基础知识

解决的问题:快速判断元素是否在集合中出现过

牺牲了空间换取了时间,因为我们要使用额外的数组,set或者是map来存放数据,才能实现快速的查找。

1)哈希索引是有一定范围的,当集合元素超过设定的数目时,会产生哈希碰撞。

2)哈希碰撞:两个或多个元素连接到同一索引。->解决方法:拉链法和线性探测法。

3)拉链法:


4)线性探测法(要保证tableSize大于dataSize):需要依靠哈希表中的空位来解决碰撞问题。

2.常见的哈希结构

    数组

    set (集合)

    map(映射)



242.有效的字母异位词

输出结果中的每个元素一定是唯一的,也就是说输出的结果的去重的, 同时可以不考虑输出结果的顺序。

跟着写了一遍,不难。

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容