青岛达内的小编总结,全文行文是基于面试题的分析基础之上的,具体实践过程中,还是得具体情况具体分析,且各个场景下需要考虑的细节也远比本文所描述的任何一种解决方法复杂得多。
何谓海量数据处理?
基于海量数据上的存储、处理、操作。
何谓海量,就是数据量太大,导致要么是无法在较短时间内迅速解决,要么是数据太大,导致无法一次性装入内存。
那解决办法呢?
针对时间,我们可以采用巧妙的算法搭配合适的数据结构,如Bloom filter/Hash/bit-map/堆/数据库或倒排索引/trie树
针对空间,无非就一个办法:大而化小,分而治之(hash映射),把规模大化为规模小的,各个击破
至于单机及集群问题,通俗点来讲
单机就是处理装载数据的机器有限(只需考虑CPU,内存,硬盘的数据交互)
集群,机器有多台,适合分布式处理,并行计算(更多考虑节点和节点间的数据交互)。
处理海量数据,不外乎
分而治之/hash映射 + hash统计 + 堆/快速/归并排序
双层桶划分
Bloom filter/Bitmap;
Trie树/数据库/倒排索引;
外排序;
分布式处理之Hadoop/Mapreduce.
本文第一部分、从set/map谈到hashtable/hash_map/hash_set,简要介绍下set/map/multiset/multimap,及hash_set/hash_map/hash_multiset/hash_multimap之区别(万丈高楼平地起,基础最重要),而本文第二部分,则针对上述那6种方法模式结合对应的海量数据处理面试题分别具体阐述。
从set/map到hashtable/hashmap/hashset
序列式容器
vector/list/deque/stack/queue/heap
关联式容器。关联式容器又分为set(集合)和map(映射表)两大类,还有第3类关联式容器,如hashtable(散列表)
类似关联式数据库,每笔数据或每个元素都有一个键值(key)和一个实值(value),即所谓的Key-Value(键-值对)
set/map
set,同map一样,所有元素都会根据元素的键值自动被排序,值得注意的是,两者都不允许两个元素有相同的键值。
不同的是:set的元素不像map那样可以同时拥有实值(value)和键值(key),set元素的键值就是实值,实值就是键值,而map的所有元素同时拥有实值(value)和键值(key),pair的第一个元素被视为键值,第二个元素被视为实值。
hash_set/hash_map
hash_set/hash_map,两者的一切操作都是基于hashtable之上。不同的是,hash_set同set一样,同时拥有实值和键值,且实质就是键值,键值就是实值,而hash_map同map一样,每一个元素同时拥有一个实值(value)和一个键值(key),所以其使用方式,和上面的map基本相同。
以上就是青岛达内给大家做的内容详解,更多关于UI的学习,请继续关注青岛达内