> For the complete documentation index, see [llms.txt](https://mabuxi.gitbook.io/mabuxi/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mabuxi.gitbook.io/mabuxi/leetcode-summary/data-structure/hashtable.md).

# HashTable

## 几种用法

1. 给定一堆二维点 `int[][] obstacles`，需要判断是否存在一个点。这时，可以将二维点以 `String`的形式存在 `Set` 里，比如 `obstacles[i][0] + "," + obstalces[i][1]`，这样将来可以将点转换成该形式进行判断。

## 经典题目

[*874 Walking Robot Simulation*](https://leetcode.com/contest/weekly-contest-94/problems/walking-robot-simulation/)

```java
class Solution {
    public int robotSim(int[] commands, int[][] obstacles) {
        int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int x = 0, y = 0, angle = 0;
        Set<String> set = new HashSet<>();
        for (int[] o : obstacles) {
            set.add(o[0] + "," + o[1]);
        }
        int max = 0;
        for (int command: commands) {
            if (command == -1) {
                angle += 1;
                angle = angle == 4 ? 0 : angle;
            } else if (command == -2) {
                angle -= 1;
                angle = angle == -1 ? 3 : angle;
            } else {
                while (command-- > 0 && (!set.contains((x + dirs[angle][0]) + "," + (y + dirs[angle][1])))) {
                    x += dirs[angle][0];
                    y += dirs[angle][1];
                }
            }
            max = Math.max(max, x * x + y * y);
        }
        return max;
    }
}
```

[ *711 Number of Distinct Islands II*](https://leetcode.com/problems/number-of-distinct-islands-ii/description/)

```java
// 二维矩阵 hash 计算方法。

class Solution {
    public int numDistinctIslands2(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
        int n = grid.length;
        int m = grid[0].length;
        Set<String> set = new HashSet<>();
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    List<int[]> points = new ArrayList<>();     // store [row, col] pair
                    dfs(i, j, n, m, grid, points);              // dfs to find all connected points
                    
                    String hash = getHash(points, n + m);
                    set.add(hash);
                }
            }
        }
        return set.size();
    }
    
    // Hash Function:
    // For a point (x, y), there are 8 different ways which have the same shape
    // (x, y), (x, -y), (-x, y), (-x, -y)
    // (y, x), (y, -x), (-y, x), (-y, -x)
    // Thus, for a particular point list, we would have 8 potential different point lists with the same shape.
    
    // The process would be : we iterate through different point list,
    // for each point list, we first find min_x and min_y within it,
    // and then make all the points align to the top left corner, which means (x, y) -> (x - min_x, y - min_y)
    // during this process, we use another array to help us record the relative hash for each point based on x, y and seed.
    
    // After get the hash array, we then sort it in ascending order, and make it a string.
    // Then we store the min string among all 8 hash strings to be the final result hash.
    
    private String getHash(List<int[]> points, int seed) {
        String hash = "";
        int[] xm = new int[points.size()];
        int[] ym = new int[points.size()];
        int[] out = new int[points.size()];
        
        for (int c = 0; c < 8; c++) {
            for (int i = 0; i < points.size(); i++) {
                int y = points.get(i)[0];
                int x = points.get(i)[1];
                update(xm, ym, i, c, x, y);
            }
            int mx = xm[0], my = ym[0];
            for (int i = 1; i < xm.length; i++) {
                mx = Math.min(mx, xm[i]);
                my = Math.min(my, ym[i]);
            }
            for (int i = 0; i < points.size(); i++) {
                out[i] = (xm[i] - mx) * seed + (ym[i] - my);
            }
            Arrays.sort(out);
            String candidate = Arrays.toString(out);
            if (hash.compareTo(candidate) < 0) hash = candidate;
        }
        return hash;
    }
    
    private void update(int[] xm, int[] ym, int index, int c, int x, int y) {
        if (c == 0) {
            xm[index] = x;
            ym[index] = y;
        } else if (c == 1) {
            xm[index] = x;
            ym[index] = -y; 
        } else if (c == 2) {
            xm[index] = -x;
            ym[index] = y;
        } else if (c == 3) {
            xm[index] = -x;
            ym[index] = -y;
        } else if (c == 4) {
            xm[index] = y;
            ym[index] = x;
        } else if (c == 5) {
            xm[index] = y;
            ym[index] = -x;
        } else if (c == 6) {
            xm[index] = -y;
            ym[index] = x;
        } else {
            xm[index] = -y;
            ym[index] = -x;
        }
    }
    
    private void dfs(int row, int col, int n, int m, int[][] grid, List<int[]> points) {
        if (row < 0 || row >= n || col < 0 || col >= m || grid[row][col] == 0) return;
        points.add(new int[] {row, col});
        grid[row][col] = 0;         // set 0 to avoid infinite loop
        dfs(row + 1, col, n, m, grid, points);
        dfs(row - 1, col, n, m, grid, points);
        dfs(row, col + 1, n, m, grid, points);
        dfs(row, col - 1, n, m, grid, points);
    }
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mabuxi.gitbook.io/mabuxi/leetcode-summary/data-structure/hashtable.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.