Simply, Hash is a mapping relationship between data content and data storage addresses. For example, a number of strings should be stored in a Haxi table, I hope to locate a particular string in the table in the table in O (1), we can use an array to implement the Haxi table, find some kind of function Sting -> INTEGER, records P = f (s), where P is an integer, S is a string, and P is the subscript in the array. This can be calculated if the S is positioned in an array as needed to directly depend on the function P = F (s). Add a string in the Haxi table. It is also similar, calculates the position in the array according to the value of the string, and then puts the string in. But this function (becoming a Haxi function) is difficult to find, find a one-to-one function is almost impossible, so it is often used to use a non-one Haxi function. For example, for the above example, we can design a simple Haxi function, we set f (s) defined as the ASCII code of the respective characters of S and the remainder of N, where n is the length of our array, we assume The N elements need to store up to the Haxi table. However, this Haxi function has an obvious shortcoming, such as for strings S1 = "ABC" and S2 = "ACB", obviously calculated Haxi function values is the same, but only one element can be stored in a location. If S1 is first placed in the location P1 of the Haxi table, then the S2 is placed in the Haxi table, this time, because P2 = f (S2) = P1 is calculated, the position of S2 should be placed has been occupied by S1, so it will appear trouble. This is called "conflict." A simple way to resolve this conflict is that because P1 has been occupied by S1, we will see P1 1, if this location is empty, then put it in S2, otherwise you will continue to see P1 2, ... I have always found a vacancy. Suppose we put S2 in P1 1, but at this time you have to join S3, and f (s3) is equal to P1 1, S3 position is occupied by S2, we can continue to see P1 2, P1 3 ... Whether it is empty until it is found in S3, and so on. When looking up S2, we first calculate S2 according to F (S2), and then we look at the P1 position, then we look at the elements at P1 position, found not S2 (S1), so we continue to see P1 1, P1 2, ... has been discontinued until the S2 is found, or to the end of the tail, or it can be aborted, and the latter case indicates that S2 is not in the table. Obviously, if there is too much in the conflict, the efficiency of the Haxi table will decline. In fact, the Haxi function in the example I just raised is very bad, so the possibility of conflict has a lot. If you find a better Haxi function, the efficiency of the Haxi table is still very high. As for the method of finding the Haxi function, there is also some principles based on the specific data type and application, here is not one of them ~~
