问题

可比较泛型怎么新建数组？

自己写基于AVL树的散列表时，在自动扩容的时候需要遍历AVL树的Key，所以需要AVL树提供一个方法返回一个Key数组以遍历，初始实现如下：

     /**
     * 用于辅助遍历Key
     */
    class KeyQueue {
        private K[] queue;

        private int size;

        public KeyQueue(int capacity) {
            queue = (K[]) new Object[capacity];
            size = 0;
        }

        public void enQueue(K key) {
            queue[size] = key;
            size++;
        }

        public Object[] getQueue() {
            return queue;
        }
    }

    /**
     * 返回所有键
     *
     * @return 键数组
     */
    public Object[] getKeyArray() {
        KeyQueue queue = new KeyQueue(size);
        preOrder(root, queue);
        return queue.getQueue();
    }

    private void preOrder(Node node, KeyQueue queue) {
        if (node == null) {
            return;
        }
        queue.enQueue(node.key);
        preOrder(node.left, queue);
        preOrder(node.right, queue);
    }

KeyQueue 类是用于辅助装载Key的，因为自带的数组你不知道它装多少了，所以在此基础上简单封装了一个size变量。

但是这样会报错：

"C:\Program Files\JetBrains\IntelliJ IDEA 2019.3.5\jbr\bin\java.exe" "-javaagent:C:\Program Files\JetBrains\IntelliJ IDEA 2019.3.5\lib\idea_rt.jar=13543:C:\Program Files\JetBrains\IntelliJ IDEA 2019.3.5\bin" -Dfile.encoding=UTF-8 -classpath D:\Project\DataStructureJavaLearn2021\out\production\data_structure_java top.minuy.structure.hash.Test
Test AVLTreeHashTable : 
Exception in thread "main" java.lang.ClassCastException: class [Ljava.lang.Object; cannot be cast to class [Ljava.lang.Comparable; ([Ljava.lang.Object; and [Ljava.lang.Comparable; are in module java.base of loader 'bootstrap')
  at top.minuy.structure.map.AVLTreeMap$KeyQueue.<init>(AVLTreeMap.java:59)
  at top.minuy.structure.map.AVLTreeMap.getKeyArray(AVLTreeMap.java:79)
  at top.minuy.structure.hash.AVLTreeHashTable.resize(AVLTreeHashTable.java:214)
  at top.minuy.structure.hash.AVLTreeHashTable.add(AVLTreeHashTable.java:92)
  at top.minuy.structure.hash.AVLTreeHashTable.add(AVLTreeHashTable.java:10)
  at top.minuy.structure.hash.Test.testHashTable(Test.java:61)
  at top.minuy.structure.hash.Test.main(Test.java:21)

Process finished with exit code 1

然后到网上看看有没有可以new一个可比较对象数组，发现好像并没有。

只能放弃这个想法。

解决

后来想了下，数组其实也是一种类，还不知道哪里有关于可比较泛型数组这方面的内容介绍，个人猜测转不了的原因应该是它们两个数组类Object[] 和 K[] 没有继承关系，但是想了下，它们里面的元素有继承关系。所以应该是在元素级别强转，而不是数组级别。

所以AVLTreeMap中的改为：

    /**
     * 用于辅助遍历Key
     */
    class KeyQueue {
        private Object[] queue;

        private int size;

        public KeyQueue(int capacity) {
            queue = new Object[capacity];
            size = 0;
        }

        public void enQueue(Object key) {
            queue[size] = key;
            size++;
        }

        public Object[] getQueue() {
            return queue;
        }
    }

    /**
     * 返回所有键
     *
     * @return 键数组
     */
    public Object[] getKeyArray() {
        KeyQueue queue = new KeyQueue(size);
        preOrder(root, queue);
        return queue.getQueue();
    }

    private void preOrder(Node node, KeyQueue queue) {
        if (node == null) {
            return;
        }
        queue.enQueue(node.key);
        preOrder(node.left, queue);
        preOrder(node.right, queue);
    }

就返回Object数组

但是AVLTreeHashTable这边因为类型原因报错了

    /**
     * 重新分配散列表大小
     *
     * @param capacity 新的散列表大小
     */
    private void resize(int capacity) {
        // System.out.println("resize : " + capacity + " size : " + size);

        AVLTreeMap<K, V>[] newTable;
        newTable = new AVLTreeMap[capacity];
        for (int i = 0; i < newTable.length; i++) {
            newTable[i] = new AVLTreeMap<>();
        }

        K[] keyArray;
        for (int i = 0; i < table.length; i++) {
            AVLTreeMap<K, V> map = table[i];
            keyArray = (K[])map.getKeyArray();
            for (int j = 0; j < keyArray.length; j++) {
                // System.out.println("["+j+"]"+keyArray[j] + " ");
                int hash = getHash(keyArray[j]);
                newTable[hash].add(keyArray[j], map.get(keyArray[j]));
            }
//            System.out.println();
//            System.out.println("index : " + i);
        }

        table = newTable;
    }

这句：

keyArray = (K[])map.getKeyArray();

也是一样的错误，我们应该从数组中取出元素后再强转。

所以修改为：

    /**
     * 重新分配散列表大小
     *
     * @param capacity 新的散列表大小
     */
    private void resize(int capacity) {
        // System.out.println("resize : " + capacity + " size : " + size);

        AVLTreeMap<K, V>[] newTable;
        newTable = new AVLTreeMap[capacity];
        for (int i = 0; i < newTable.length; i++) {
            newTable[i] = new AVLTreeMap<>();
        }

        Object[] keyArray;
        for (int i = 0; i < table.length; i++) {
            AVLTreeMap<K, V> map = table[i];
            keyArray = map.getKeyArray();
            for (int j = 0; j < keyArray.length; j++) {
                // System.out.println("["+j+"]"+keyArray[j] + " ");
                K key = (K) keyArray[j];
                int hash = getHash(key);
                newTable[hash].add(key, map.get(key));
            }
//            System.out.println();
//            System.out.println("index : " + i);
        }

        table = newTable;
    }

其中这句：

K key = (K) keyArray[j];

就是在元素从数组中取出后才强转，因为运行时它原本就是AVLTreeMap那边返回的K类型的元素，所以可以强转成功~

至此，问题解决~~