Chapitre avancé du programmeur : Le tempérament de la table de hachage

M. Zhang Yanpo a rejoint Baishan Cloud Technology en 2016 et est principalement responsable de la recherche et du développement sur le stockage d'objets, de la distribution des données dans les salles informatiques, ainsi que de la réparation et de la résolution de problèmes. Dans le but d'atteindre un niveau de stockage de données de 100 Po, il a dirigé l'équipe pour achever la conception, la mise en œuvre et le déploiement d'un système de stockage distribué à l'échelle du réseau, séparant les données « froides » et « chaudes », réduisant ainsi le coût des données froides à 1,2. fois la redondance.

M. Zhang Yanpo a travaillé pour Sina de 2006 à 2015 et était responsable de la conception de l'architecture, de la formulation du processus de collaboration, de la spécification du code et de la formulation des normes de mise en œuvre ainsi que de la mise en œuvre de la plupart des fonctions du service de stockage cloud Cross-IDC PB. A travaillé pour prendre en charge les services de stockage internes de Sina tels que Weibo, microdisque, vidéo, SAE, musique, téléchargements de logiciels, etc. De 2015 à 2016, il a été expert technique senior chez Meituan et a conçu une solution de stockage objet de 100 Po dans les salles informatiques : Concevoir et mettre en œuvre une stratégie de réplication multi-copies à haute concurrence et haute fiabilité, optimiser le code d'effacement pour réduire la surcharge d'E/S de 90 %.

Dans le développement de logiciels, une table de hachage équivaut à placer aléatoirement n clés dans b compartiments pour réaliser le stockage de n données dans b espaces unitaires.

Nous avons trouvé quelques phénomènes intéressants dans la table de hachage :

Le modèle de distribution des clés dans la table de hachage

Quand la table de hachage Lorsque le nombre de clés et de buckets est le même (n/b=1) :

• 37% des buckets sont vides

• 37 % des buckets ne contiennent qu'une seule clé

• 26 % des buckets ont plus d'une clé (conflit de hachage)

La figure suivante le montre intuitivement. Lorsque n=b=20, le nombre de clés dans chaque bucket dans la table de hachage (trier les buckets selon le nombre de clés) :

Souvent, nous utilisons la table de hachage. La première impression est la suivante : si les clés sont placées au hasard dans tous les compartiments, le nombre de clés dans le compartiment sera relativement uniforme et le nombre attendu de clés dans chaque compartiment est de 1.

En fait, la répartition des clés dans le bucket est très inégale lorsque n est petit ; lorsque n augmente, il deviendra progressivement moyen.

L'impact du nombre de clés sur le nombre de buckets dans la catégorie 3

Le tableau suivant montre comment la valeur de n/b affecte la catégorie 3 lorsque b reste inchangé et n augmente. La proportion du nombre de buckets (le taux de conflit est la proportion de buckets contenant plus d'1 clé) :

Pour être plus intuitif, on utilise la figure suivante pour montrer le taux de seau vide et la tendance changeante du taux de conflit avec la valeur n/b :

L'impact du nombre de clés sur l'uniformité du seau

Les ensembles de chiffres ci-dessus C'est une valeur de référence significative lorsque n/b est petit, mais à mesure que n/b augmente progressivement, le nombre de seaux vides et de seaux avec une clé est presque 0, et la plupart des compartiments contiennent plusieurs clés.

Lorsque n/b dépasse 1 (un bucket permet de stocker plusieurs clés), notre objet d'observation principal devient le modèle de répartition du nombre de clés dans le bucket.

Le tableau suivant montre le degré d'inégalité lorsque n/b est grand et que le nombre de clés dans chaque compartiment a tendance à être uniforme.
Afin de décrire le degré d'inégalité, nous utilisons le rapport entre le nombre maximum et minimum de clés dans le seau ((le plus petit)/le plus) pour l'exprimer.

Le tableau suivant répertorie la distribution des clés à mesure que n augmente lorsque b = 100.

On constate qu'à mesure que le nombre moyen de clés dans le seau augmente, l'inégalité de sa répartition diminue progressivement.

和空bucket或1个key的bucket的占比不同n/b，均匀程度不仅取决于n/b的值，也受b值的影响，后面会提到。

未使用统计中常用的均方差法去描述key分布的不均匀程度，是因为软件开发过程中，更多时候要考虑最坏情况下所需准备的内存等资源。

Facteur de charge : n/b

Un concept couramment utilisé dans les tables de hachage, le facteur de charge α=n/b, est utilisé pour décrire le caractéristiques des tables de hachage.

Habituellement, sur la base de la table de hachage du stockage mémoire, son n/b ≤0,75. Ce paramètre permet non seulement d'économiser de l'espace, mais également de maintenir le taux de conflit de clé relativement bas. Un faible taux de conflit signifie un déplacement de hachage à basse fréquence et l'insertion de la table de hachage sera plus rapide.

线性探测是一个经常被使用的解决插入时hash冲突的算法，它在1个bucket出现冲突时，按照逐步增加的步长顺序向后查看这个bucket后面的bucket，直到找到1个空bucket。因此它对hash的冲突非常敏感。

Dans ce scénario de n/b=0,75, si la détection linéaire n'est pas utilisée (comme l'utilisation d'une liste chaînée dans le bucket pour enregistrer plusieurs clés), environ 47 % des buckets sont vides ; si vous utilisez la détection linéaire, sur ces 47 % de seaux, environ la moitié des seaux seront remplis par détection linéaire.

在很多内存hash表的实现中，选择n/b＝<p><strong>Conseils sur les fonctionnalités de la table de hachage : </strong></p>

• La table de hachage elle-même est un algorithme qui échange une certaine quantité d'espace pour plus d'efficacité. Une faible surcharge de temps (O(1)), une faible perte d'espace et un faible taux de conflit ne peuvent pas être obtenus en même temps

• Les tables de hachage ne conviennent que pour le stockage de données de mémoire pure ; structures :
  

• La table de hachage échange de l'espace contre une augmentation de la vitesse d'accès ; le gaspillage d'espace disque est insupportable, mais un petit gaspillage de mémoire est acceptable ; 🎜 >

• Les tables de hachage ne conviennent qu'aux supports de stockage à accès aléatoire rapide. Le stockage des données sur le disque dur utilise principalement des btrees ou d'autres structures de données ordonnées.

• La plupart des langages de haut niveau (table de hachage intégrée, jeu de hachage, etc.) maintiennent n/b≤
  Lorsque n/b est petit, la table de hachage ne distribuera pas les clés uniformément.

Load Factor：n/b>1

另外一种hash表的实现，专门用来存储比较多的key，当 n/b>1n/b1.0时，线性探测失效（没有足够的bucket存储每个key)。这时1个bucket里不仅存储1个key，一般在一个bucket内用chaining，将所有落在这个bucket的key用链表连接起来，来解决冲突时多个key的存储。

链表只在n/b不是很大时适用。因为链表的查找需要O(n)的时间开销，对于非常大的n/b，有时会用tree替代链表来管理bucket内的key。

n/b值较大的使用场景之一是：将一个网站的用户随机分配到多个不同的web-server上，这时每个web-server可以服务多个用户。多数情况下，我们都希望这种分配能尽可能均匀，从而有效利用每个web-server资源。

这就要求我们关注hash的均匀程度。因此，接下来要讨论的是，假定hash函数完全随机的，均匀程度根据n和b如何变化。

n/b 越大，key的分布越均匀

当 n/b 足够大时，空bucket率趋近于0，且每个bucket中key的数量趋于平均。每个bucket中key数量的期望是：

avg=n/b

定义一个bucket平均key的数量是100%：bucket中key的数量刚好是n/b，下图分别模拟了 b=20，n/b分别为 10、100、1000时，bucket中key的数量分布。

可以看出，当 n/b 增大时，bucket中key数量的最大值与最小值差距在逐渐缩小。下表列出了随b和n/b增大，key分布的均匀程度的变化：

结论:

计算

上述大部分结果来自于程序模拟，现在我们来解决从数学上如何计算这些数值。

每类bucket的数量

空bucket数量

对于1个key, 它不在某个特定的bucket的概率是 (b−1)/b
所有key都不在某个特定的bucket的概率是( (b−1)/b)n

已知：

空bucket率是：

空bucket数量为：

有1个key的bucket数量

n个key中，每个key有1/b的概率落到某个特定的bucket里，其他key以1-(1/b)的概率不落在这个bucket里，因此，对某个特定的bucket，刚好有1个key的概率是：

刚好有1个key的bucket数量为：

多个key的bucket

剩下即为含多个key的bucket数量：

key在bucket中分布的均匀程度

类似的，1个bucket中刚好有i个key的概率是：n个key中任选i个，并都以1/b的概率落在这个bucket里，其他n-i个key都以1-1/b的概率不落在这个bucket里，即：

这就是著名的二项式分布。

我们可通过二项式分布估计bucket中key数量的最大值与最小值。

通过正态分布来近似

当 n, b 都很大时，二项式分布可以用正态分布来近似估计key分布的均匀性：

p=1/b，1个bucket中刚好有i个key的概率为：

1个bucket中key数量不多于x的概率是：

所以，所有不多于x个key的bucket数量是：

bucket中key数量的最小值，可以这样估算: 如果不多于x个key的bucket数量是1，那么这唯一1个bucket就是最少key的bucket。我们只要找到1个最小的x，让包含不多于x个key的bucket总数为1, 这个x就是bucket中key数量的最小值。

计算key数量的最小值x

一个bucket里包含不多于x个key的概率是：

Φ(x) 是正态分布的累计分布函数，当x-μ趋近于0时，可以使用以下方式来近似：

这个函数的计算较难，但只是要找到x，我们可以在[0~μ]的范围内逆向遍历x，以找到一个x 使得包含不多于x个key的bucket期望数量是1。

x可以认为这个x就是bucket里key数量的最小值，而这个hash表中，不均匀的程度可以用key数量最大值与最小值的差异来描述: 因为正态分布是对称的，所以key数量的最大值可以用 μ + (μ-x) 来表示。最终，bucket中key数量最大值与最小值的比例就是：

（μ是均值n/b）

程序模拟

以下python脚本模拟了key在bucket中分布的情况，同时可以作为对比，验证上述计算结果。

import sysimport mathimport timeimport hashlibdef normal_pdf(x, mu, sigma):
    x = float(x)
    mu = float(mu)

    m = 1.0 / math.sqrt( 2 * math.pi ) / sigma
    n = math.exp(-(x-mu)**2 / (2*sigma*sigma))return m * ndef normal_cdf(x, mu, sigma):
    # integral(-oo,x)

    x = float(x)
    mu = float(mu)
    sigma = float(sigma)    # to standard form
    x = (x - mu) / sigma

    s = x
    v = x    for i in range(1, 100):
        v = v * x * x / (2*i+1)
        s += v    return 0.5 + s/(2*math.pi)**0.5 * math.e ** (-x*x/2)def difference(nbucket, nkey):

    nbucket, nkey= int(nbucket), int(nkey)    # binomial distribution approximation by normal distribution
    # find the bucket with minimal keys.
    #
    # the probability that a bucket has exactly i keys is:
    #   # probability density function
    #   normal_pdf(i, mu, sigma)
    #
    # the probability that a bucket has 0 ~ i keys is:
    #   # cumulative distribution function
    #   normal_cdf(i, mu, sigma)
    #
    # if the probability that a bucket has 0 ~ i keys is greater than 1/nbucket, we
    # say there will be a bucket in hash table has:
    # (i_0*p_0 + i_1*p_1 + ...)/(p_0 + p_1 + ..) keys.
    p = 1.0 / nbucket
    mu = nkey * p
    sigma = math.sqrt(nkey * p * (1-p))

    target = 1.0 / nbucket
    minimal = mu    while True:

        xx = normal_cdf(minimal, mu, sigma)        if abs(xx-target) < target/10:            break

        minimal -= 1

    return minimal, (mu-minimal) * 2 / (mu + (mu - minimal))def difference_simulation(nbucket, nkey):

    t = str(time.time())
    nbucket, nkey= int(nbucket), int(nkey)

    buckets = [0] * nbucket    for i in range(nkey):
        hsh = hashlib.sha1(t + str(i)).digest()
        buckets[hash(hsh) % nbucket] += 1

    buckets.sort()
    nmin, mmax = buckets[0], buckets[-1]    return nmin, float(mmax - nmin) / mmaxif __name__ == "__main__":

    nbucket, nkey= sys.argv[1:]

    minimal, rate = difference(nbucket, nkey)    print &#39;by normal distribution:&#39;
    print &#39;     min_bucket:&#39;, minimal    print &#39;     difference:&#39;, rate

    minimal, rate = difference_simulation(nbucket, nkey)    print &#39;by simulation:&#39;
    print &#39;     min_bucket:&#39;, minimal    print &#39;     difference:&#39;, rate

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!