hash function

Basic concepts:

• out = f( in )
• in input field, which is infinite by default; out output field, finite
• The same input returns the same output value (there is no random component in the hash function)
• Different inputs may produce the same output (hash collision, very low probability)
• Hashing of hash function: the hash function should maintain the uniformity and discreteness of the output domain (the approximate input data mapped to the output domain is uniform and discrete in the whole output domain, that is, the output is very different)

application
Example: Statistics of a large amount of data
If there are 1 ~ 2 ^ 32 data, count the number of different numbers

• General idea: use hashMap (key, value). Key is the corresponding number and value is the number of times the key appears. However, if there are many keys, it will lead to a large use of space
• Optimization: first use the hash function to map the numbers, and then perform the modulo 100 operation on the mapping results. Divide the data into 100 parts for statistics respectively, and free up space for the next statistics after statistics. In this way, the space can be reduced by 100 times

Hashtable

Basic concepts:

• An integer value is obtained from the data through the hash function, and the data is stored in the corresponding hash table: that is, the value obtained by the hash function is modeled on the value corresponding to the hash table, and then stored in the corresponding position after calculation, which is convenient for searching
• According to the hash property of the hash function, the length of the hash linked list should grow evenly
  
• As shown in the figure, the hash table of module 16. If the amount of data is too large, choose to expand to module 32 and recalculate the corresponding position of each node
• The time complexity of adding, deleting and searching data in the hash table is O(1), but the constant term is very large. If the maximum length of N data links in the hash table is k, the time complexity of capacity expansion is (logn), n times with K as the bottom

Title: design RandomPool structure

• Idea: adding and deleting operations can be completed in HashMap. The important thing is to realize the function of random return
  (1) Create two hashmaps, one is < key, size >, the other is < size, key >, where size is the number of elements in the current hash table
  (2) The getRandom operation can generate numbers in the range of 0 ~ size - 1 through random numbers, and obtain the key through the hash table of < size, key >
  (3) In the delete operation, in order to ensure the continuity of 0 ~ size - 1 position, fill the element of the last position into the delete position, and the size is minus one

    public static class Pool<Key>{
        private HashMap<Key, Integer> keyIndexMap;
        private HashMap<Integer, Key> indexKeyMap;
        private int size;

        public Pool(){
            //initialization
            this.keyIndexMap = new HashMap<>();
            this.indexKeyMap = new HashMap<>();
            this.size = 0;
        }

        public void insert(Key key){
            if (!keyIndexMap.containsKey(key)){
                //Establish a direct bijection relationship between key and size
                keyIndexMap.put(key, size);
                indexKeyMap.put(size, key);
                size++;
            }
        }

        public void delete(Key key){
            if (keyIndexMap.containsKey(key)){
                //To ensure the continuity of 0 ~ size - 1
                //Delete < key, deleteindex > from keyIndexMap and add < lastkey, deleteindex >
                //Delete < lastindex, lastkey > and update < deleteindex, lastkey > in indexKeyMap
                int deleteIndex = keyIndexMap.get(key);
                int lastIndex = --size;
                Key lastKey = indexKeyMap.get(lastIndex);
                keyIndexMap.remove(key);
                indexKeyMap.remove(lastIndex);
                keyIndexMap.put(lastKey, deleteIndex);
                indexKeyMap.put(deleteIndex, lastKey);
            }
        }

        public Key getRandom(){
            if (size == 0){
                return null;
            }
            // Random number from 0 to size - 1
            int random = (int)(Math.random() * size);
            return indexKeyMap.get(random);
        }
    }

    public static void main(String[] args) {
        Pool<String> pool = new Pool<>();
        pool.insert("l");
        pool.insert("j");
        pool.insert("k");
        System.out.println(pool.getRandom());
    }

• Result demonstration