在散列排序中，每一个桶代表的是散列函数返回的唯一值。散列排序并没有创建n个桶，而是创建了k个桶，随着k的增长，散列排序的速度不断加快。散列排序的关键在于散列函数hash(e)返回的整数值，对于每个元素e，如果ai≤aj，那么hash(ai)≤hash(aj)。
例4-13定义了散列函数hash(e)，这个函数计算仅仅包含了小写字母的元素。它将字符串的前三个字符转换成一个值（基准值为26），对于字符串"abcdefgh"，它的前三个字符（"abc"）被抽取出来然后转换得0*676+1*26+2=28。这个字符串将插入到标为28的桶中。
例4-13：散列排序的hash和numBuckets函数
散列排序的性能和桶的大小以及输入的规模有关，具体可参考表4-5。我们将一个使用了三中值方法来选择pivotIndex的快速排序和散列排序进行比较，并且给出了一个可以比较的排序时间。
注意在17 576个桶，n＞8192个元素的情况下，散列排序的性能要优于快速排序（并且这个趋势随着n的增长继续保持）。但是，仅仅只有676个桶，n＞32768（平均每个桶48个元素）的话，散列排序随着数据集的增长，执行插入排序的开销也不断增长，速度越来越慢。事实上，在26个桶，n＞256的情况下，随着n的加倍，散列排序所需的时间增加3倍，在桶很少时，散列排序的性能是O(n2)。