Hashing

title: Hashing (DSA) description: Hash tables aur hashing concepts

Key se direct memory location calculate karna — O(1) average access.

Hash Function

java exampleWoHoTech

int hashCode(String key, int tableSize) {
    int hash = 0;
    for (char c : key.toCharArray())
        hash = (hash * 31 + c) % tableSize;
    return hash;
}

Collision Resolution — Chaining

class HashTable<K, V> { private static final int SIZE = 16; private LinkedList<K[]>[] table; @SuppressWarnings("unchecked") HashTable() { table = new LinkedList[SIZE]; } private int hash(K key) { return Math.abs(key.hashCode()) % SIZE; } void put(K key, V value) { int idx = hash(key); if (table[idx] == null) table[idx] = new LinkedList<>(); for (K[] entry : table[idx]) { if (entry[0].equals(key)) { entry[1] = value; return; } } table[idx].add((K[]) new Object[]{key, value}); } }

HashMap Problems

Two Sum

int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int complement = target - nums[i]; if (map.containsKey(complement)) return new int[]{map.get(complement), i}; map.put(nums[i], i); } return new int[]{}; }

Longest Subarray with Sum K

int longestSubarraySum(int[] arr, int k) { Map<Integer, Integer> prefixMap = new HashMap<>(); prefixMap.put(0, -1); int maxLen = 0, prefixSum = 0; for (int i = 0; i < arr.length; i++) { prefixSum += arr[i]; if (prefixMap.containsKey(prefixSum - k)) maxLen = Math.max(maxLen, i - prefixMap.get(prefixSum - k)); prefixMap.putIfAbsent(prefixSum, i); } return maxLen; }

Group Anagrams

java exampleWoHoTech

List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> map = new HashMap<>();
    for (String s : strs) {
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        String key = new String(chars);
        map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
    }
    return new ArrayList<>(map.values());
}

title: Hashing (DSA) description: Hash tables aur hashing concepts

Key se direct memory location calculate karna — O(1) average access.

Hash Function

java exampleWoHoTech

int hashCode(String key, int tableSize) {
    int hash = 0;
    for (char c : key.toCharArray())
        hash = (hash * 31 + c) % tableSize;
    return hash;
}

Collision Resolution — Chaining

HashMap Problems

Two Sum

Longest Subarray with Sum K

Group Anagrams

java exampleWoHoTech

List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> map = new HashMap<>();
    for (String s : strs) {
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        String key = new String(chars);
        map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
    }
    return new ArrayList<>(map.values());
}

Hashing

Hash Function

Collision Resolution — Chaining

HashMap Problems

Two Sum

Longest Subarray with Sum K

Group Anagrams

Continue learning this concept

Hashing

Hash Function

Collision Resolution — Chaining

HashMap Problems

Two Sum

Longest Subarray with Sum K

Group Anagrams

Continue learning this concept