Android 位置分組優化：從 O(n²) 迴圈到空間雜湊 O(n)

原始邏輯缺陷

// 僅與「上一組」比較，導致同座標非連續點無法歸組
if (group == null || distance(group, entity) > 1) {
    group = new GroupEntity(); // 新建分組
}
group.list.add(entity);

資料未排序時，同一地點的點若不相鄰，會被錯分到不同組。

改進方案：網格雜湊分組

將經緯度映射到固定大小網格 (如 0.01 度 ≈ 1km)，以 gridKey = latGrid + "," + lngGrid 為 Key，HashMap<String, GroupEntity> 直接歸組。

public static List<GroupEntity> groupByLocation(List<ParentEntity> list, double gridSize) {
    Map<String, GroupEntity> gridMap = new HashMap<>();
    for (ParentEntity e : list) {
        int latGrid = (int) Math.floor(e.getLatitude() / gridSize);
        int lngGrid = (int) Math.floor(e.getLongitude() / gridSize);
        String key = latGrid + ":" + lngGrid;
        GroupEntity g = gridMap.computeIfAbsent(key, k -> {
            GroupEntity ng = new GroupEntity();
            ng.latitude = e.getLatitude(); // 代表點可取首點或質心
            ng.longitude = e.getLongitude();
            return ng;
        });
        g.list.add(e);
    }
    return new ArrayList<>(gridMap.values());
}

進階優化

• 自定義 hashCode/equals：在 ParentEntity 實現基於網格的 hashCode，直接用 HashSet 去重。
• K-D Tree / QuadTree：需範圍查詢或最近鄰時引入空間索引庫 (如 JTS Topology Suite Android 移植版)。
• 並行流：list.parallelStream().collect(Collectors.groupingByConcurrent(...)) 利用多核。

效能對比 (10 萬點模擬)

結論：空間雜湊將分組複雜度從 O(n²) 降至 O(n)，且天然支援無序資料，是移動端位置聚類的首選。