概念
概要数据结构（Sketch）包含H个长度为P的哈希表.
将网络流量数据建模为 （键，值） 的形式， 其中 “键” 为一个或多个数据包头中的字段， 例如源地址或源地址个目的地址的组合， “值”为存储的特征， 例如数据包的数量。
在Sketch中， 每个块表示为 T[i][j],i=1,2,...,H,j=1,2,...,P,T[i][j], i = 1,2,..., H, j = 1,2,...,P,T[i][j],i=1,2,...,H,j=1,2,...,P, 每一行iii都关联着一个哈希函数hih_ihi?, 该函数将输入的键映射到哈希空间（1,2,...,P)（1,2,...,P)（1,2,...,P) 中。
例如， 当一个新的数据（key， value）到达时， key将被h1,h2,...,hH{h_1, h_2,...,h_H}h1?,h2?,...,hH?哈希HHH次，并将值添加到每行对应的块中， 即 T[i][hi(key)]+=value,i=1,2,...HT[i][h_i(key)]+ = value, i = 1,2,...HT[i][hi?(key)]+=value,i=1,2,...H. 进行H次哈希运算的目的是为了避免不同键之间的哈希碰撞。 如果哈希函数是从一个哈希族中选择的。
那么两个不同键被哈希到同一个块中的概率是被限定的。通常， Sketch中所用的HHH个哈希函数是从k-全域哈希函数族中选择的，即
h(x)=∑i=0k?1(aixi+bi)modrmodPh(x) =\sum_{i=0}^{k-1}(a_ix^i+b_i)modrmodPh(x)=∑i=0k?1?(ai?xi+bi?)modrmodP
其中， rrr 是任意的质数， ai(≠0)a_i(\neq 0)ai?(?=0) 和 bib_ibi?是从(0,1,...,r?1)(0,1,...,r-1)(0,1,...,r?1)中随机选择的数，PPP是Sketch每一列的块数。 通过使用k?k-k?全域哈希函数， 两个不同键被哈希到同一个块中的概率为(1/P)k×H(1/P)^{k\times H}(1/P)k×H。
具有常数级的查询时间复杂度。