Java哈希表实现疑问：如何将ArrayList关联到另一ArrayList的指定索引

我是编程和Java的新手，目前正在学习Hashtable。我遇到的难题是如何将一个ArrayList关联到另一个ArrayList的某个索引，编写代码时存在困难。我的思路是将listAtIndex关联到hashTable的某个索引。最初尝试写hashTable.set(index, listAtIndex);但出现语法错误，因为set方法的第二个参数需要Pair类型对象而非ArrayList，请求帮助解决该问题。

原代码 #

class HashTable { 
    private int size;
    private ArrayList<Pair> hashTable;
    Pair Pair;  

    // Constructor
    public j(int m) {
        Pair = null;
        size = m;
        hashTable = new ArrayList<>(m);   
        for (int i = 0; i < m; i++) {           
           // hashTable.add(null);
            hashTable.add(Pair);
        }
    }
private static class Pair {  
        Integer key;
        Integer value;

        public Pair(Integer key, Integer value) {
            this.key = key;
            this.value = value;
        }
  }
private int addressOfList(Integer key) {
        int index = Math.floorMod(key, size);
        return index;
    }

public void insert(Integer key, Integer value) {
        int index = addressOfList(key);             
        Pair existingPair = hashTable.get(index);
        
        Pair newPair = new Pair(key, value);
        ArrayList<Pair> listAtIndex = new ArrayList<>();

        // if there is not jet a Pair in hashTabel.get(index)
        if(existingPair == null) {
            //connect listAtIndex to an index                    
            hashTable.set(index, newPair);  // here is where im having problems      
            listAtIndex.add(0, newPair); 
            
        }else if(newPair.key.equals(existingPair.key)) {
            listAtIndex.add(0, newPair);
        }        
   }
}

问题核心与解决方法 #

你代码里最关键的错误是哈希表的容器类型定义错了——你把hashTable定义成ArrayList<Pair>，但链地址法的哈希表，每个索引位置得存一个列表（比如ArrayList）来处理哈希冲突，所以正确类型应该是ArrayList<ArrayList<Pair>>。

修改后的完整代码 #

class HashTable { 
    private int size;
    // 修正：每个索引存Pair的ArrayList，而非单个Pair
    private ArrayList<ArrayList<Pair>> hashTable;  

    // 构造方法修正：类名是HashTable，构造方法名必须和类名一致，不能用j
    public HashTable(int m) {
        size = m;
        hashTable = new ArrayList<>(m);   
        for (int i = 0; i < m; i++) {           
            // 初始化每个索引为一个空ArrayList，不是null或单个Pair
            hashTable.add(new ArrayList<>());
        }
    }

    private static class Pair {  
        Integer key;
        Integer value;

        public Pair(Integer key, Integer value) {
            this.key = key;
            this.value = value;
        }
    }

    private int addressOfList(Integer key) {
        int index = Math.floorMod(key, size);
        return index;
    }

    public void insert(Integer key, Integer value) {
        int index = addressOfList(key);             
        // 直接获取对应索引的ArrayList，不用新建
        ArrayList<Pair> listAtIndex = hashTable.get(index);
        
        Pair newPair = new Pair(key, value);

        // 检查是否已有相同key的元素，有则替换value
        boolean keyFound = false;
        for (Pair pair : listAtIndex) {
            if (pair.key.equals(key)) {
                pair.value = value;
                keyFound = true;
                break;
            }
        }

        // 没找到相同key，就添加新元素
        if (!keyFound) {
            listAtIndex.add(newPair);
        }        
    }
}

关键修改点说明 #

• 容器类型修正：把ArrayList<Pair>改成ArrayList<ArrayList<Pair>>，这样每个索引就能存放一个Pair列表，实现链地址法解决哈希冲突。
• 构造方法修复：原构造方法名j和类名HashTable不一致，这是Java语法错误，必须改成和类名相同；同时初始化每个索引为空的ArrayList，而不是null或单个Pair。
• insert逻辑调整：
  1. 直接从hashTable拿对应索引的列表，不用每次都新建listAtIndex（原代码新建会丢失之前的元素）。
  2. 增加重复key处理：遍历列表找相同key，找到就更新value，没找到再添加新Pair。
• 移除冗余变量：删掉原代码里没用的Pair Pair;变量，命名也不规范。

这样改完后，就能实现把ArrayList关联到哈希表对应索引的需求，解决了之前的语法错误和逻辑问题。

内容的提问来源于stack exchange，提问作者happy day