java - 寻找有效的方法将哈希表的元素提取到单个数组中

Question

我创建了自己的哈希表实现，其中数组的每个条目中存储了一个链接列表(数组大小为 11)。我试图将哈希表的元素提取到单个数组中，然后对元素数组进行排序。我想过简单地将每个链表提取到结果数组中，然后稍后对数组进行排序。如下方法所示

//turns the whole hash table into an array
    private int[] toArray() {
        int sizeOfArray = 0;
        for(int i=0; i<11; i++)
        {
            //calculate the total number of elements in the hashTable
            sizeOfArray += hashMap.getList(i).size();
        }

        int[] result = new int[sizeOfArray];

        int indexRes = 0;
        //import every entry from the hash table into a single array
        for(int i=0; i<11; i++)
        {
            KeyValuePairLinkedList list = hashMap.getList(i);

            //convert the list to an array
            int[] listArray = list.toArray();
            for(int j=0; j<list.size(); j++)
            {
                result[indexRes] = listArray[j];
                indexRes++;
            }
        }
        return result;
    }

但是如果每个链表中的元素已经排序，那么我可以将这些元素合并到一个数组中，类似于合并排序算法合并两个数组的方式，但是我将合并 11 个数组而不是 2 个数组，我猜这将需要大量代码。

此外，假设我只想提取存储在哈希表中的偶数整数，然后在结果数组中对这些整数进行排序。我可以再次使用相同的方法，将整个哈希表提取到一个数组中，然后删除奇数整数，然后排序。但必须有更好的方法来做到这一点。

Answer 1

一种方法，如果数组已经排序

• 构建每个数组中第一个元素的最小堆
• 选择最小值，放入最终数组+提取下一个元素并插入堆

继续执行此操作，直到耗尽所有数组。 堆中的每个元素都有值+指向哪个数组的指针，以及它的索引。

请注意一种特殊情况，即其中一个数组已耗尽，不再需要在堆中插入。