专栏首页大数据成神之路Redis选13亿个Key,4个field还是1亿个Key,13亿*4个field?

Redis选13亿个Key,4个field还是1亿个Key,13亿*4个field?

什么是哈希

哈希hash又称为散列、杂凑等,是将任意长度的输入通过散列算法变换为固定长度的输出,最终输出也就是哈希值。这种转换是一种压缩映射。也就是说,散列值的空间通常要远小于输入控件,不同的输入可能会散列成相同的输出,所以不可能通过散列值来确定唯一的输入值。

什么是哈希表

哈希表hash table是为了将数据映射到数组中某个位置,通过数组下标访问元素以提高数据的查询速度,这种查询的平均期望时间复杂度为O(1)

例如:有4个整数分别为6、7、9、12,需要映射到数组中。

方案1:新开一个长度为13的数组,将对应值放置到对应的下标。

问题是这样做,会浪费没有被映射到的位置的空间。

方案2:采用哈希表的做法,申请长度为4的数组,将每个数的值对数组长度4取模,然后放置到对应的数组槽位中,这样就把离散的数据映射到了连续的空间,所以哈希表又称为散列表。

采用哈希表的好处是最大限度地提升空间的利用率,而且查询效率还很高。不过问题来了,如果这4个数是6、7、8、11呢?由于7和11对4取模的值都是3,所以它们会占据同一个槽位。

这种情况我们称为冲突(collision),解决冲突的方式有开放地址法、再散列法、链地址法等。Redis采用的是链地址法,简单来说,链地址法就是将有冲突的数据用一个链表给串联起来。

使用链地址法,就算有冲突也可以将有冲突的数据存储在一起。只是存储结构需要稍加变化,哈希表的每个元素将变成一个指针,指向数据链表的链表头,每次有新数据来时从链表头插入,可以达到插入的时间复杂度保持在O(1)

Redis中的字典

在Redis中,hash哈希被称为字典(dictionary),Redis的字典使用哈希表作为底层实现,一个哈希表里面可以有多个哈希表节点,而每个哈希表节点保存了字典中的一个键值对。实际上,Redis数据库底层也是采用哈希表来存储键值对的。

Redis中的哈希采用了典型的挂链解决冲突的方式,当有多个key-value键值对的键名key映射值相同时,系统会将这些键值value以单链表的形式保存,同时为了控制哈希表占用内存大小,Redis采用了双哈希表ht[2]结构,并逐步扩大哈希表容量的策略。注意,每对key-value在保存前会通过类似HASH(key) MOD N的方法计算出一个值,以确定在哈希表中所对应的位置。

Redis中一个哈希存储一条数据,一个字段field则存储一条数据中的一个属性,字段值value是属性对应的值。每个哈希hash可存储2^32-1个键值对,约40多亿个。Redis中的哈希散列类型与Java中的HashMap相似,都是一组键值对的集合,并且支持单独对其中一个键进行增删改查操作。

  • 为什么哈希更适合存储对象呢?

Redis中的哈希散列适用于存储对象,将一个对象存储在哈希类型中会占用更小的内存。将对象的每个字段存储为单个的string字符串类型,进而将一个对象存储在hash类型中,这样会占用更少的内存并能更方便的存储整个对象。

  • 为什么使用哈希会更加节省内存呢?

Redis中的哈希散列是一个string类型的fieldvalue的映射表,它的增删操作的复杂度平均为O(1)。为什么平均是O(1)呢?因为哈希的内部结构包含zipmaphash两种。hash适合存储对象,相对于对象序列化存储为string字符串类型,将对象存储在hash哈希类型中会占用更少的内存。zipmap本身并不是hashtable,由于zip压缩后可以节省hash本身所需的元数据的开销。因此zipmap的增删改查的操作复杂度为O(n)。但是域字段field的数量不多,所以说平均是O(1)。那么,为什么会占用更好的内存呢?因为对象刚开始使用的是zipmap存储的。

在新建一个哈希的时候,使用的是zipmap又称为small hash存储的。这个zipmap实际上不是我们的哈希表。但是这个zipmap相比正常的哈希实现,节省很多哈希自身所需要的元数据的存储开销。尽管zipmap的增删改查和字段的数目相关,字段太多速度会更慢。因此不建议设置过多的字段。在Redis内部,如果字段过多或者存储的值太大超过限制后,Redis会自动将zipmap替换为正常的hash来实现。

在域字段field的数量在限制范围内,并且字段值value的长度大小系统限定的字节数,此时哈希类型是用zipmap存储的,所以会比较节省内存空间。

# 配置域字段最大个数限制
hash-max-zipmap-entries 512

# 配置字段值最大字节限制
hash-max-zipmap-value 64

当满足以上两个条件时,哈希表key会被压缩,否则将按照正常的哈希结构来存储。

Redis中哈希与集合的异同点

set以普通的key-value键值对的方式存储,可以设置过期时间,时间复杂度为O(1),每执行一个set就会在Redis中多出一个key

hset是以哈希散列表的形式存储,超时时间只能设置在键key上,单个域field不能设置过期时间。时间复杂度为O(n)n是单个哈希上的field域个数。所以,单个哈希并不适合存储大量的字段field,过多的字段field会比较消耗CPU。但优点在于散列表存储会比较节省内存。

实际应用中,应该使用set集合存储单个大文本的非结构化数据,使用hset哈希散列表来存储结构化数据。

Redis中对哈希的操作

Redis中对hash类型的操作

hset key field value

  • 将哈希表key中的字段field的值设置为value,若key不存在则创建后赋值,若域field已存在则覆盖。
  • Redis中hset命令用于为哈希表中的字段赋值,如果哈希表不存在则创建并进行字段赋值,否则原字段值将被新字段值所覆盖。
  • 若字段是哈希表中新建的字段且字段值设置成功则返回1,若哈希表中域字段已经存在且旧值被新值覆盖成功则返回0。
$ redis-cli
127.0.0.1:6379> hset username "junchow"
(error) ERR wrong number of arguments for 'hset' command

# 错误:set或map的size为0,一个没有值的set或map。

选13亿个Key,4个field还是1亿个Key,13亿*4个field?现在心里有数了吗?

本文分享自微信公众号 - 大数据技术与架构(import_bigdata)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-11-06

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Spark面对OOM问题的解决方法及优化总结

    map执行中内存溢出代表了所有map类型的操作,包括:flatMap,filter,mapPatitions等。shuffle后内存溢出的shuffle操作包括...

    王知无
  • 实战 | MySQL Binlog通过Canal同步HDFS

    本文来自:http://bigdatadecode.club/MysqlToHDFSWithCanal.html

    王知无
  • HBase调优|HBase + G1GC 性能调优

    目前小米已经在线上开始大规模使用G1垃圾回收算法,在论坛中也看到一些朋友在讨论使用G1碰到的各种各样的问题,这里打算写一篇文章记录下调G1的一些经验。 先传送门...

    王知无
  • 哈希算法的用途

    简单来说, 哈希算法就是将任意长度的字符串通过计算转换为固定长度的字符串, 不对, 不光字符串, 应该说是将任意长度的二进制串转换为固定长度的二进制串, 这个转...

    烟草的香味
  • 哈希碰撞是什么,怎么解决

    Hash是一种校验方法, 其中应用最广为人知的就是 HashMap。 当然Hash算法并不完美,有可能两个不同的原始值在经过哈希运算后得到同样的结果, 这样就是...

    PhoenixZheng
  • 学界 | 中科院NIPS 2017论文提出深度离散哈希算法,可用于图像检索

    机器之心
  • 深度离散哈希算法,可用于图像检索!

    -免费加入AI技术专家社群>> 智能感知与计算研究中心李琦博士提出了一种深度离散哈希算法(discrete hashing algorithm),该算法认为学习...

    企鹅号小编
  • LeetCode | 你不得不了解的哈希算法 !

    问大家一个问题 。如果手机上存储了 1000 个联系人 ,现在要你给小詹打个电话 ,跟他说 ,他老婆喊他回家吃饭 。你会怎么做 ?

    小小詹同学
  • 哈希

    我们知道,通过对数组进行直接寻址(Direct Addressing),可以在 O(1) 时间内访问数组中的任意元素。所以,如果存储空间允许,可以提供一个...

    对弈
  • 图像检索:基于内容的图像检索技术(四)

    基于树结构的最近邻搜索方法和基于哈希的最近邻搜索方法在理论计算机科学、机器学习以及计算机视觉中是一个很活跃的领域,这些方法通过将特征空间划分成很多小的单元,以此...

    用户3578099

扫码关注云+社区

领取腾讯云代金券