散列表
2021-05-02 本文已影响0人
张_何
- 散列表又称 hash 表
- 散列表底层是一个数组,数组中存放的是(key,value),它本质是空间换时间
- 散列表是怎么存储的呢?
假设散列表的长度是 10,那么 mask 的值就是散列表的长度-1 也就是 9, IOS 中散列表的存储是根据给定的 key 值 & 上 mask 值然后得出一个索引,如果这索引对应的数组中的元素为空,就将要存储的值存到这个数组的这个索引的位置,如果这个索引对应的素组元素有值,那么就将索引值-1,如果还有值就再减一,直到找到空的位置,然后存进去. - 散列表是怎么取的呢?
ios 中根据给定的 key 值算出索引值,然后根据算出的索引值,取出对应的元素,如果元素中的 key 值和给定的key 值一样,那么就将元素中的值其取出,如果取出的 key值和给定的 key 不一样,那么就将索引减一继续,直到找到与给定 key 值一样的,将其取出. - 一旦扩容会将之前的元素清掉,因为mask 已经变了
- 散列表为什么效率比数组高,因为最坏情况也就是便利一遍数组
- 不同语言散列表的算法可能不一样,其核心算法就是根据给定的 key 算出一个索引,这个算法有可能是求& 或者求%或者其他的算法.
