• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

Swift里Set(一)辅助类型

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

_UnsafeBitset


是一个固定大小的 bitmap,用来确定指定位置是否有元素存在。

HashTable

具体的 hash 碰撞算法在HashTable里实现,目前使用的是简单的开放地址法,使用算法是Linear probing

HashTable 的属性

其实只有若干个 UInt,每一位用来表示状态,指定位置有没有被占用。

  @usableFromInline
  internal var words: UnsafeMutablePointer<Word>

算法相关

  • maxLoadFactor

      /// The inverse of the maximum hash table load factor.
      private static var maxLoadFactor: Double {
        @inline(__always) get { return 3 / 4 }
      }
    
  • 寻找下一个可用的位置

      @inlinable
      internal func nextHole(atOrAfter bucket: Bucket) -> Bucket {
        _internalInvariant(isValid(bucket))
        // Note that if we have only a single partial word, its out-of-bounds bits
        // are guaranteed to be all set, so the formula below gives correct results.
        var word = bucket.word
        if let bit =
          words[word]
            .complement
            .subtracting(elementsBelow: bucket.bit)
            .minimum {
          return Bucket(word: word, bit: bit)
        }
        var wrap = false
        while true {
          word &+= 1
          if word == wordCount {
            _precondition(!wrap, "Hash table has no holes")
            wrap = true
            word = 0
          }
          if let bit = words[word].complement.minimum {
            return Bucket(word: word, bit: bit)
          }
        }
      }
    
  • 根据 hash 值确定位置
    其实就是取hash值的后几位

      internal func idealBucket(forHashValue hashValue: Int) -> Bucket {
        return Bucket(offset: hashValue & bucketMask)
      }
    

Delegate

@usableFromInline
internal protocol _HashTableDelegate {
  func hashValue(at bucket: _HashTable.Bucket) -> Int
  func moveEntry(from source: _HashTable.Bucket, to target: _HashTable.Bucket)
}

_HashTable 只是实现了 hash 冲突,计算 hash 值、移动元素,都让外部实现。在删除元素时会用到。


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap