简单实现hashSet -- 应用篇

王海东_011c · · 808 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

简单实现hashSet -- 应用篇

写这篇文章的起因:

  • 在使用golang和php的时候我们经常会判断一个变量是否在map或者数组中;
  • 在php中的时候我们经常使用in_array()来判断,这里是我们经常用的。

其实用in_array()这个函数就是对数组进行遍历判断是否存在时间复杂度是log(n)

一般数组不是太大也就这样了;

  • 但是在golang中并没有封装这个函数,这个需要我们自己去封装。

如果也是用循环的方式去判断变量是否存在,那是不是感觉很low,也就是这个原因引出了这篇文章

  1. 在php和golang中都适用,主要原理是判断key是否存在

    // 在golang中可以这样

type HashSet struct {

        set map[interface{}}]bool

}

func NewHashSet() *HashSet {

return &HashSet{make(map[interface{}]bool)}

}

func (set *HashSet) Add(k interface{}) bool {

_, ok := set.set[k]

set.set[i] = true

return !ok //False if it existed already

}

func (set *HashSet) Get(k interface{}) bool {

_, found := set.set[k]

return found //true if it existed already

}

func (set *HashSet) Remove(k interface{}) {

delete(set.set, k)

}


    // InArray 函数就简单的模拟了in_array 函数

    // 需要注意的是,在设置 $HashSet 的时候需要设置在key 中,

    // 例 :

$HashSet = [

"a" => true,

"b" => true,

];

    function InArray(&$HashSet,$key) {

        return isset($HashSet[$key]);

}

    var_dump(InArray($HashSet,"b"))

    // 当然这里也可以不用InArray 封装,直接用 isset,这里只是为了举例子

    // 如果是正常数组

    $HashSet2= [

"a" ,"b"

];

    // 可以使用 array_flip() 函数(交换数组中的键和值。)

    // 再使用isset进行判断

总结

  1. 就是数的key与value调换,利用map和数组中的key的唯一性来判断

  2. 判断key是否存在的时间复杂度是 O(1);

参考文献

[1] Go 语言简单实现HashSet


有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:王海东_011c

查看原文:简单实现hashSet -- 应用篇

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

808 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传