知识卡片

普通读书笔记卡 · 5654.c.1.a.2.a.2.a.25 · 生成模型:未记录

字符串前缀分桶需保序且校验

理解等级:中级

把至少三个小写拉丁字母组成的字符串前三字符按26进制映射到 0..17575,字典序不同前缀会落入有序桶,同前缀仍需桶内比较完整字符串。给定固定桶数,数据不断增长或高度偏斜时,桶内插入排序可退化到二次。

03227直接读取前三字节且假设字母在 a..z;短字符串、其他字符、编码规则或大小写顺序不符合假设时可能越界或破坏顺序,应验证并设计终止符及排序规则。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      前三个字符转换成一个值(基准值为26),对于字符串"abcdefgh",它的前三个字符("abc")被抽取出来然后转换得0*676+1*26+2=28。这个字符串将插入到标为28的桶中。 例4-13:散列排序的hash和numBuckets函数 散列排序的性能和桶的大小以及输入的规模有关,具体可参考

    参考来源

    - 位置:《算法技术手册》第4章《变种》(spine1527;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1490.html;u102-ch04-026)。 - 结论依据:102全文、03227代码和03228性能表实读。 - 原始内容:前三个字符转换成一个值(基准值为26),对于字符串"abcdefgh",它的前三个字符("abc")被抽取出来然后转换得0*676+1*26+2=28。这个字符串将插入到标为28的桶中。 例4-13:散列排序的hash和numBuckets函数 散列排序的性能和桶的大小以及输入的规模有关,具体可参考