海量数据

字数：338字 | 预计阅读时长：1分钟

问题

  • 存储、运算(排序等)

背景知识

  • stl 容器

    • 序列式
    • 关联式
      • 类比 关联式数据库
      • 非关联数据库，document里也是kv
      • 底层
        • 红黑树
          • set/map/multiset/multimap
            • multi即允许重复
            • insert_equal()而非insert_unique()
        • hashtable
          • hash_set/hash_map/hash_multiset/hash_multimap
          • HashSet实现了Set接口，HashMap实现了Map接口，HashSet扩展了HashMap，底层存储相同
          • hashtable和hashmap ： 前者继承Dictionary类、synchronized、不允许键或值为 null、Enumerator是fail-safe

​

  • hashcode
    • equals为true，hashcode一定相等，反之不成立
    • (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)

解决方案

  • 分而治之/hash映射 + hashmap统计 + 堆/快速/归并排序；

    • 负载均衡算法

      • 轮循算法（Round Robin）、哈希算法（HASH）、最少连接算法（Least Connection）、响应速度算法（Response Time）、加权法（Weighted）

      • hash

        • 取余

        • 一致性

          • 分布式系统负载均衡的首选算法
          • Hash 算法的一个衡量指标是单调性（ Monotonicity ）： 新增的key被hash到新的机子上
          • 圆圈

    • topk

      • 堆排序
        • N个无重值topk的复杂度，N*O(logK)
        • TOP10小，用最大堆，TOP10大，用最小堆
      • trie tree

    • 同一个key在两台机子

      • 全hash，同一个key到一台。然后分布式架构处理，如MapReduce，最后合并
      • 暴力，每台都算出来，再加和
  • 双层桶划分
  • Bloom filter/Bitmap
  • Trie树/数据库/倒排索引
  • 外排序
  • 分布式处理之Hadoop/Mapreduce
本文作者： yuqing wang
本文链接： https://satyrswang.github.io/2021/10/06/海量数据/
版权声明： 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处！
赏

thanks for tips

支付宝
微信

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

关心算法、cs、网络、投资, 闲听历史、看史评 wechat satyrsh