Data structure Hash table, C language solution

A hash table (also known as a hash table) is a data structure that is directly accessed based on the key value. That is, it accesses records by mapping key values to a location in the table to speed up lookups. This mapping function is called a hash function, and the array that holds the records is called a hash table.

Given table m, there is a function f(key), for any given keyword value key, if the address of the record containing the keyword can be obtained after substituting the function into the key, then table m is called a hash table, and the function f(key) is a hash function.

Common Approach: Hash functions make access to a data sequence faster and more efficient, and data elements are located more quickly through hash functions.

In practice, different hash functions need to be used according to different situations, and the factors usually considered are: (1) the time required to calculate the hash function. (2) The length of the keyword.

3) The size of the hash table. (4) The distribution of keywords. (5) The frequency of searching for records.

Lookup performance: The process of finding a hash table is basically the same as that of a tab. Some key codes can be found directly by the address converted by the hash function, while some key codes have a conflict on the address obtained by the hash function, and need to be found according to the method of dealing with the conflict.

Of the three methods of dealing with conflicts presented, the post-collision lookup is still the process of comparing a given value to a keycode. Therefore, the measure of hash table lookup efficiency is still measured by the average lookup length.

The hash address of the above keyword sequence, calculated by the hash function of the remainder method, is (12,12,8,9,0,2,11,3,2,2).

Insert 25 t[12] position first, 51 is also 12, so then probe (12+1) mod 13 = 0, insert t[0] position, insert t[8], insert t[9], insert t[9], insert 26 into t[0], and find occupied, and then probe (0+1) mod 13 = 1, insert t[1], 67 insert t[2], 11 insert t[11], 16 insert t[3], insert 54 into t[2], find t[2] occupied, (2+1) mod 13 = 3, t[3] Still occupied, probe again, (2+2)mod 13 = 4, insert t[4], 41 found t[2] occupied, t[3] t [4] also occupied, (2+3) mod 13 = 5, t[5] open, inserted, the result is as follows.

Address Space sequence.

1. The storage structure of all hash tables is a hash function.

The hashing technique is to establish a definite correspondence f between the storage location of the record and its keywords, so that each keyword key corresponds to a storage location f (key).

This correspondence f is called the hash function, also known as the hash function. In this way, hashing techniques are used to store records in a contiguous piece of storage called a hash table or hash table. Then, the record storage location corresponding to the keyword is called the hash address.

The most suitable solution problem for hashing techniques is to find records that are equal to a given value. For lookups, the comparison process is simplified and the efficiency is greatly improved. However, the hashing technology department has many capabilities in conventional data structures, such as comparing the same keywords and corresponding to many records, which is not suitable for hashing technology; Hash lists are also not suitable for range lookups, etc.

Ideally, the address calculated by the hash function is different for each keyword, but in reality, this is just an ideal. The market will come across two keywords key1!= key2, but there is f(key1) = f(key2), this phenomenon is called a conflict.

Collisions can cause lookup errors, so they can be made as few as possible by designing hash functions, but they cannot be avoided entirely.

A hash table is a hash store, and its hash value is obtained by a hash algorithm. A hash value is similar to a subscript value in an array, but the objects in the hash table are not stored in a continuous location. By finding the hash value, it is easy to find the object in the corresponding location.

In general, the hash degree is optimal (the balance point of query efficiency and memory usage)!!

Generally speaking, it is a sequential storage structure.

I hit, I ad, I hit me, I hit me, how much often think, often think V-shaped, V think V.

Solution: hi=(h(key)+di) mod m, i=1,2,3....k(k<=m-1) m is the length of the hash table, di=1,2,3,4,..

m-1, where m=19, linear detection rehashing is the incremental sequence of slip foci di=1,2,3,..m-1

19%13=6,01%13=1,23%13=10,14%13=1,55%13=3,20%13=7 No conflicts.

When processing 84, 84%13=6, but 6 units have been occupied, there is a conflict, call the conflict handling function h1=(h(84)+1) mod 19=7, but 7 units are occupied again, call the conflict handling function again to get h2=(h(84)+2) mod 19=8, no conflict.

The following will not be listed with a debate, and the answer I calculated will be pasted below, which may be wrong, welcome to correct!

**It's not easy to align horizontally, so I'll put it vertically.

Address unit keyword.

I hope my answer helps you understand

, reload factor = 9 13

3. The average search length of a successful search asl= 11 13

Solution: hi=(h(key)+di).

modm,i=1,2,3...k(k<=m-1)

m is the length of the hash table, di=1,2,3,4,..m-1, which is m=19, and the linear detection rehash is an incremental sequence di=1,2,3,..m-1

There were no conflicts.

When processing 84, 84%13=6, but 6 units are already occupied, and there is a conflict, and the conflict handling function h1=(h(84)+1) is called

mod19=7, but unit 7 is occupied again, and the conflict handling function is called again to get h2=(h(84)+2).

mod19=8, no conflict.

The following will not be listed one by one, the following will post the answer I calculated, there may be mistakes, welcome to correct!

**It's not easy to align horizontally, so I'll put it vertically.

Address unit. Keywords.

In fact, linear detection and hashing are more special, that is, to find the first free address unit under the collision unit before the hungry tomb, and you don't need to calculate it and scan it directly with your eyes to know where to put the next one.

I hope my answer helps you understand