按哈希表排序（也按树数和HashMap排序）

三天前，我考虑过将计数和树排序结合起来。 与同事讨论后，我们做出以下决定：使用HashMap代替TreeSet（TreeSet与它有什么关系，您可以在下面看到）。 但这对我来说似乎还是有些不足，所以我决定实现自己的哈希表并查看它的结果。 结果对我来说似乎很有趣。

对于数组中许多唯一元素的功效相对较小的情况，这三种类型的排序都非常有用（在我们查看测试结果后，这将变得很清楚）。

树数排序

我们构建Steam树（键，数量），其中键负责数组元素，而数量是此数组元素的重复次数。 树是自然平衡的，例如黑色和红色。

此外，一切都是合乎逻辑的。 我们将数组的所有元素添加到Pair中，然后在树中查找Pair（为避免重新创建对象，我们使用先前创建的Pair，从中我们更改了Key。这里我们对Number并不感兴趣，因为我们只通过Key寻找匹配项。 如果已经存在这样的密钥，则增加数量，否则添加新的对（密钥，1）。

我们重写数组，每次删除顶点，并记下Key的次数与Number一样多。

为了不实现树本身，对于所描述的算法，我使用了TreeSet，它适用于黑红色树。

使用HashMap

我们将数组元素存储为键，并将重复次数存储为键值。

使用我自己的哈希表

我决定采用开放式寻址的方法。 在哈希表中，我们存储Pair类的对象，其中第一个是键，第二个是重复次数。 自然地，添加了一个构造函数，该构造函数采用表的初始大小和负载因子。 哈希函数是最简单的：我们对密钥进行取模，在重复访问的情况下，添加一个（该单元工作得很好，因为密钥数组是最有序的，最后我们必须使用标准的快速排序对所有密钥进行排序，因为在表中它们可能变成无序的） ） 因此，我们可以说这是哈希和其他类型的组合。

碰撞

显然，可能会发生冲突，这将严重影响确定哈希值的时间以及对生成的哈希数组排序的速度（排序或几乎排序的数据排序速度更快）。 但这就是问题：随着表的扩展，我们的哈希值ff发生了变化。 因此，专门选择此类数据变得更加困难。 此外，有可能使负载系数和膨胀系数随机（当然是在一定范围内），这将使得不可能预先选择导致碰撞的值。 好吧，如果在一个表中某些数据导致冲突，那么在重新哈希后，可以显着减少冲突次数（几次）。 弱点将是数字的阶乘，但是它们的数字小得令人难以置信（例如，最多2 ^ 31，其中只有11个（不包括0））。

加密散列不适合我们，因为使用散列，您可以忘记几乎是有序的散列数组（按键排序）。

工作时间

树计数排序：在最坏的情况下，对于O（n log n），最多为线性时间。
哈希表排序：哈希时间+哈希数组排序的复杂度（可能会有所不同，具体取决于所选的算法和实现，因此在此不做任何说明）。 由于使用哈希函数和各种可能的哈希排序方法，因此很难估算复杂度。 这个问题需要进一步的研究，但是很明显，在最坏的情况下（当输入数据在特定的执行阶段被有意地匹配到特定的哈希函数时），运算时间将为O（n ^ 2）。

记忆中有什么？

树计数排序将需要O（distinct（n））额外的内存
对于哈希表，我们需要O（distinct（n））内存+内存来对哈希排序（取决于所选算法）。

这是将对象数组分类为1000万个elts时得到的随机数的毫秒数，范围为[0; x]：

在测试中，我的哈希表中的负载因子= 0.75，初始容量= 20，该表每次都会加倍

对于x = 10：
2044年-集成
285-树数（Usatov排序）
276-HashMap（Usatov-Prokurat排序）
140-使用我的哈希表（使用MyHashTable进行的Usatov-Prokurat排序）

x = 100：
2406-内置
455-计数树
283-HashMap
134-哈希表

x = 1_000：
2171-集成
930-计数树
380-HashMap
209-哈希表

x = 10_000
2879-整合
1666-计数树
634-HashMap
326-哈希表

x = 100_000
4045-集成
2899-计数树
866-HashMap
762-哈希表

x = 1_000_000
4997-集成
5762-计数树
2505- HashMap
1294-哈希表

x = 10_000_000
5083-集成
11480-计数树
5099-HashMap
3240-哈希表

正如我在开始时所说的那样，这些排序最适合于数组中许多元素的功率相对于数组大小足够小的情况。

还值得注意的是，内置排序对有序（几乎有序）数据（或相反顺序的数组）的工作速度要快得多，但是我的方法对随机数的处理速度更快。

树数排序：

static void usatovSort(Integer[] arr) { TreeSet<MyPair> tree = new TreeSet<>(); MyPair temp; MyPair mp = new MyPair(); for (int i : arr) { temp = mp; temp.first = i; temp = tree.ceiling(temp); if (temp != null && temp.first == i) //   , .    ,      temp.second++; else tree.add(new MyPair(i, 1)); } int ptr = 0; while (!tree.isEmpty()) { temp = tree.pollFirst(); for (int i = 0; i < temp.second; i++) arr[ptr++] = temp.first; } } 

通过HashMap排序：

  static void usatovProkuratSortUsingHashMap(Integer[] arr) { HashMap<Integer, Integer> hm = new HashMap<>(); Integer temp; for (Integer i : arr) { temp = hm.get(i); if (temp == null) hm.put(i, 1); else hm.put(i, temp + 1); } ArrayList<Integer> keys = new ArrayList<>(hm.keySet().size()); keys.addAll(hm.keySet()); keys.sort(Comparator.naturalOrder()); int ptr = 0; for (Integer i : keys) for (int j = 0; j < hm.get(i); j++) arr[ptr++] = i; } 

排序我的哈希表：

  static void usatovProkuratSortUsingMyHashTable(Integer[] arr) { MyHashTable mht = new MyHashTable(); for (Integer i : arr) mht.add(i); MyPair[] res = mht.getPairs(); int ptr = 0; Arrays.sort(res, Comparator.comparingInt(o -> o.first)); for (MyPair mp : res) for (int i = 0; i < mp.second; i++) arr[ptr++] = mp.first; } 

哈希表的实现：

 public class MyHashTable { private MyPair[] hashArr; private double count = 0; private double loadFactor = 0.5; private double expansivity = 2; private static final int DEFAULT_CAPACITY = 20; public MyHashTable() { hashArr = new MyPair[DEFAULT_CAPACITY]; } public MyHashTable(double loadFactor) { hashArr = new MyPair[DEFAULT_CAPACITY]; this.loadFactor = loadFactor; } public MyHashTable(int capacity) { hashArr = new MyPair[capacity]; } public MyHashTable(int capacity, double loadFactor) { hashArr = new MyPair[capacity]; this.loadFactor = loadFactor; } public MyHashTable(int capacity, double loadFactor, double expansivity) { hashArr = new MyPair[capacity]; this.loadFactor = loadFactor; this.expansivity = expansivity; } public MyPair[] getPairs() { MyPair[] pairs = new MyPair[(int) count]; int ptr = 0; for (MyPair i : hashArr) if (i != null) pairs[ptr++] = i; return pairs; } public MyPair get(int key) { int add = 0; while (true) if (hashArr[(key + add) % hashArr.length].first == key) { return hashArr[(key + add) % hashArr.length]; } else if (add++ == hashArr.length) return null; } public void add(int key) { if (count / hashArr.length >= loadFactor) grow(); int add = 0; while (true) { if (hashArr[(key + add) % hashArr.length] == null) { hashArr[(key + add) % hashArr.length] = new MyPair(key, 1); count++; return; } if (hashArr[(key + add) % hashArr.length].first == key) { hashArr[(key + add) % hashArr.length].second++; return; } add++; } } public void add(MyPair newMP) { if (count / hashArr.length >= loadFactor) grow(); int add = 0; while (true) { if (hashArr[(newMP.first + add) % hashArr.length] == null) { hashArr[(newMP.first + add) % hashArr.length] = newMP; count++; return; } if (hashArr[(newMP.first + add) % hashArr.length].first == newMP.first) { hashArr[(newMP.first + add) % hashArr.length].second += newMP.second; return; } add++; } } private void grow() { MyPair[] oldHash = hashArr; hashArr = new MyPair[(int) (expansivity * hashArr.length)]; for (MyPair i : oldHash) if (i != null) innerAdd(i); } private void innerAdd(MyPair mp) { int add = 0; while (true) { if (hashArr[(mp.first + add) % hashArr.length] == null) { hashArr[(mp.first + add) % hashArr.length] = mp; return; } if (hashArr[(mp.first + add) % hashArr.length].first == mp.first) { hashArr[(mp.first + add) % hashArr.length].second += mp.second; return; } add++; } } } 

蒸汽等级：

 public class MyPair implements Comparable<MyPair> { public int first; public int second; public MyPair() { } public MyPair(int first, int second) { this.first = first; this.second = second; } @Override public int compareTo(MyPair o) { return first - o.first; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; MyPair myPair = (MyPair) o; return first == myPair.first; } @Override public int hashCode() { return first; } }