1. Hash algorithm

  1. Hash algorithm: The hash algorithm transforms a piece of data into a flag that has a very tight relationship to each byte of the source data. Another characteristic of Hash algorithms is that it is difficult to find reverse patterns.
  2. Collision (hash collision) : It is possible to get the same hash address for different keywords.
  3. Uniform hash function: For any keyword in the keyword set, the probability of mapping to any address in the address set through the hash function is equal.
  4. What are the hash algorithms?
  • Direct addressing: Take the value of a keyword or a linear function of the keyword as a hash address. H(key)=key or H(key)= a·key +b, where a and b are constants (such hash functions are called self functions)
  • Divisor remainder method. If the key is divided by a number p that is not larger than m, the remainder is the hash address: H(key) = key MOD p,p<=m. Not only can the key directly modular, but also after folding, square take medium operations modular. The choice of p is very important, generally take prime number or m, if p is not chosen well, it is easy to cause collision.
  1. A: When designing the hash hash of a class, we cannot guarantee that the hash value of each element will be different, which will cause hash conflicts. There are four ways to resolve hash collisions: Develop addressing methods: Since the current location does not hold the conflicting elements, find an empty location to store the hash value (if the current index conflicts, put the conflicting elements in index+1). Rehash: A different Hash algorithm computes a Hash value, and stores the value if there is no conflict (for example, the first Hash algorithm computes the Hash value of the first letter of the name, if there is a conflict, computes the Hash value of the second letter of the name, and if the conflict is resolved, puts the value in an array). Linked address method: Each array contains a single linked list, and when a Hash conflict occurs, the value of the conflict is simply inserted into the list as a new node (HashMap resolves conflicts). Public overflow zone method: Stores all the conflicting values in another sequence table. If there is no corresponding value in the current table, the sequence search is performed in the overflow zone.

HashCode is used in Java

  1. The existence of hashCode is mainly used for quick lookup, such as Hashtable, HashMap, etc. HashCode is used to determine the storage address of the object in the hash storage structure.
  2. If two objects are the same, that applies to equals(java.lang.object), then the hashCode of the two objects must be the same.
  3. If the equals method of an object is overridden, then the hashCode of the object should be overridden as well, and the resulting hashCode must be the same as that used in the equals method, otherwise it will violate point 2 above.
  4. The fact that two objects have the same hashCode does not necessarily mean that they are the same, and does not necessarily apply to equals(java.lang.object), except that they are stored “in the same basket” in a hash storage structure such as Hashtable.
package java.lang; Public class Object {/** * returns the hash value of this Object. * This method is supported to improve the performance of hash tables such as those provided by java.util.hashtable * {@link java.util.hashmap}. * <p> *hashThe general convention for Code is: * <ul> * <li> Multiple calls to the same object during the execution of a Java applicationhashWhen using the Code method, * must consistently return the same integer, provided that the information used to compare objects to Equals has not been modified. * The integer need not be consistent from one execution of an application to another execution of the same application. * <li> If two objects are equal according to the equals(Object) method, * then each of the two objects is calledhashThe Code methods must all produce the same integer result. * <li> If two objects are not equal according to the equals(java.lang.object) method, * is called on either of themhashThe Code method does not require that different integer results be generated. * However, programmers should be aware that generating different integer results for unequal objects can improve hash table performance. * </ul> * <p> * actually, defined by the Object classhashThe Code method does return different integers for different objects. * (This is typically done by converting the object's internal address to an integer, * but the JavaTM programming language does not require this implementation trick.) * * @returnA hash code value for this object. * @see java.lang.Object#equals(java.lang.Object)
     * @see     java.lang.System#identityHashCode
     */
    public native int hashCode();
}
Copy the code