散列表

概念

散列表本身就是為了查找

原始人思想

散列表思想

6%5 是?1

1%5 也是1 沖突

沖突怎么辦？

線性探測法

就往后找，1跑到索引為2

然后查找，可以發現，只要沒沖突就只用查找1次

然后你想找10的話，發現索引為0的地方什么都沒有，所以查1次為空就結束

然后這個方法空間用的多，但查的快

然后這里失敗情況解釋一下

1是%之后為0的情況

3是%之后為1的情況，也就是說要往后找3次才看見空

這上面是沒有循環的情況下的

當然，這個表是可以循環的，比如我們想插個24，就會到索引為0這里，查找的話也一樣

刪除

這里把9刪了的話，4就查不到了，怎么辦

那就可以把9下面弄個False，變成邏輯刪除就行，并不是真正的刪除

然后還有二種散列表存放的方法

上面這些ab上面的都是題目會給你的

然后還要一些處理沖突的方法

這寫的什么玩意，具個例子就知道了

這里9占了索引為4的之后，4不得不去索引為5的地方

因此索引為5的本來是為所有余數為5的數開放，但現在余數為4的也放進去了，所以就是上面說的即向同義詞開放，也對非同義詞開放

拉鏈法

這種不僅要串起來，還會排個序，不過也可以不排序

線性探測法的小例子

這里第2行是余數，第三行是查找次數

然后是找失敗的，找空位置

裝填因子

裝填因子就是看表放的多滿，這里4/7

?散列函數如果是對2取余肯定比對100取余更容易發生沖突

做題

1

2

這里到索引為4的時候，是邏輯刪除，并不是真正的刪除，所以還得往后查找，查找到索引0是空，所以查找了2次

c