search
HomeBackend DevelopmentC#.Net TutorialClassic conflict handling of hash tables (hash tables) in data structures

Hash is to establish a certain correspondence relationship f between the storage location of the record and its keywords, so that each keyword key corresponds to a storage location f (key), and establishes the mutual relationship between the keyword and the storage location. Correspondence relationship, this relationship f is called hash function (hash function). The editor of this article mainly talks about the conflict handling problem of hash function.


Classic conflict handling of hash tables (hash tables) in data structures

During the search process, the number of key code comparisons depends on the number of conflicts. The fewer conflicts, the higher the search efficiency. , there will be many conflicts, and the search efficiency will be low. Therefore, factors that affect the number of conflicts are factors that affect search efficiency. There are the following three factors that affect the number of conflicts:

1. Whether the hash function is uniform;

2. The method of handling conflicts;

3. The filling factor of the hash table .

The filling factor of the hash table is defined as: α = the number of elements filled in the table / the length of the hash table

α is a sign factor of the degree of filling of the hash table. Since the table length is a fixed value, α is proportional to the "number of elements filled in the table". Therefore, the larger α is, the more elements are filled in the table, and the greater the possibility of conflict; the smaller α, The fewer elements that populate the table, the less likely there will be conflicts.

In fact, the average search length of the hash table is a function of the filling factor α, but different methods of handling conflicts have different functions.

The methods to resolve hash conflicts generally include:

NO.1 Open addressing method

The so-called open addressing method means that once a conflict occurs, look for the next empty address. As long as the hash table is large enough, the empty hash address can always be found and the record will be stored.

Formula: f(key)=(f(key) di)%m(di=1,2,3….m-1)

For example, the keyword set is { 12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34}, the table length is 12. Hash function f(key) = key mod 12.

When calculating the first five numbers {12, 67, 56, 16, 25}, they are all hash addresses without conflict and are stored directly; when calculating key = 37, it is found that f(37) = 1. At this time, it conflicts with the location of 25. So apply the above formula f(37) = (f(37) 1) mod 12 =2,. So 37 is stored at the location with index 2. The next 22, 29, 15, and 47 have no conflicts and are deposited normally. At 48, we calculate f(48) = 0, which conflicts with the 0 position of 12. It doesn't matter, we f(48) = (f(48) 1) mod 12 = 1, which conflicts with the position of 25. . So f(48) = (f(48) 2) mod 12 = 2, there is still a conflict... There will be no vacancies until f(48) = (f(48) 6) mod 12 = 6. As shown in the table below.

##6756

NO.2 Re-hashing method

For hash tables, multiple hash functions can be prepared in advance.

Formula: fi(key)=RHi(key)(i=1,2,3...,k)

Here RHi is a different hash function, you can divide and leave the remainder, Folding, squaring and centering are all used. Whenever a hash address conflict occurs, a different hash function is used for calculation.

This method can prevent keyword aggregation, but it also increases the calculation time accordingly.

NO.3 Chain address method (zipper method)

Store all records whose keywords are synonyms in a single linked list. This type of table is called a synonym sublist. Only pointers to the front of all synonym sublists are stored in the hash table. For the keyword set {12, 67, 56, 16, 25, 37, 22, 29, 15, 47, 48, 34}, use the same 12 as the remainder as before and perform the division and remainder method to get the structure below.

Classic conflict handling of hash tables (hash tables) in data structures

NO.4 Establish a public overflow area

This method is to find a new address for you when you are working, and create a public overflow area for all conflicting keywords. overflow area for storage.

As far as the previous example is concerned, there are three keywords 37, 48, and 34 that conflict with the previous keyword positions, so store them in the overflow table. As shown below.

Classic conflict handling of hash tables (hash tables) in data structures

When searching, after calculating the hash address of the given value through the hash function, it is first compared with the corresponding position in the basic table. If they are equal, search Success; if not equal, perform a sequential search in the overflow table. If there are very few conflicting data compared to the basic table, the structure of the common overflow area is still very high for search performance.

[Recommended Courses: C Related Courses]

Serial number 0 1 2 3 4 5 6 7 8 9 10 11
Keywords 12 25

16




The above is the detailed content of Classic conflict handling of hash tables (hash tables) in data structures. For more information, please follow other related articles on the PHP Chinese website!

Statement
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Beyond the Hype: Assessing the Current Role of C# .NETBeyond the Hype: Assessing the Current Role of C# .NETApr 30, 2025 am 12:06 AM

C#.NET is a powerful development platform that combines the advantages of the C# language and .NET framework. 1) It is widely used in enterprise applications, web development, game development and mobile application development. 2) C# code is compiled into an intermediate language and is executed by the .NET runtime environment, supporting garbage collection, type safety and LINQ queries. 3) Examples of usage include basic console output and advanced LINQ queries. 4) Common errors such as empty references and type conversion errors can be solved through debuggers and logging. 5) Performance optimization suggestions include asynchronous programming and optimization of LINQ queries. 6) Despite the competition, C#.NET maintains its important position through continuous innovation.

The Future of C# .NET: Trends and OpportunitiesThe Future of C# .NET: Trends and OpportunitiesApr 29, 2025 am 12:02 AM

The future trends of C#.NET are mainly focused on three aspects: cloud computing, microservices, AI and machine learning integration, and cross-platform development. 1) Cloud computing and microservices: C#.NET optimizes cloud environment performance through the Azure platform and supports the construction of an efficient microservice architecture. 2) Integration of AI and machine learning: With the help of the ML.NET library, C# developers can embed machine learning models in their applications to promote the development of intelligent applications. 3) Cross-platform development: Through .NETCore and .NET5, C# applications can run on Windows, Linux and macOS, expanding the deployment scope.

C# .NET Development Today: Trends and Best PracticesC# .NET Development Today: Trends and Best PracticesApr 28, 2025 am 12:25 AM

The latest developments and best practices in C#.NET development include: 1. Asynchronous programming improves application responsiveness, and simplifies non-blocking code using async and await keywords; 2. LINQ provides powerful query functions, efficiently manipulating data through delayed execution and expression trees; 3. Performance optimization suggestions include using asynchronous programming, optimizing LINQ queries, rationally managing memory, improving code readability and maintenance, and writing unit tests.

C# .NET: Building Applications with the .NET EcosystemC# .NET: Building Applications with the .NET EcosystemApr 27, 2025 am 12:12 AM

How to build applications using .NET? Building applications using .NET can be achieved through the following steps: 1) Understand the basics of .NET, including C# language and cross-platform development support; 2) Learn core concepts such as components and working principles of the .NET ecosystem; 3) Master basic and advanced usage, from simple console applications to complex WebAPIs and database operations; 4) Be familiar with common errors and debugging techniques, such as configuration and database connection issues; 5) Application performance optimization and best practices, such as asynchronous programming and caching.

C# as a Versatile .NET Language: Applications and ExamplesC# as a Versatile .NET Language: Applications and ExamplesApr 26, 2025 am 12:26 AM

C# is widely used in enterprise-level applications, game development, mobile applications and web development. 1) In enterprise-level applications, C# is often used for ASP.NETCore to develop WebAPI. 2) In game development, C# is combined with the Unity engine to realize role control and other functions. 3) C# supports polymorphism and asynchronous programming to improve code flexibility and application performance.

C# .NET for Web, Desktop, and Mobile DevelopmentC# .NET for Web, Desktop, and Mobile DevelopmentApr 25, 2025 am 12:01 AM

C# and .NET are suitable for web, desktop and mobile development. 1) In web development, ASP.NETCore supports cross-platform development. 2) Desktop development uses WPF and WinForms, which are suitable for different needs. 3) Mobile development realizes cross-platform applications through Xamarin.

C# .NET Ecosystem: Frameworks, Libraries, and ToolsC# .NET Ecosystem: Frameworks, Libraries, and ToolsApr 24, 2025 am 12:02 AM

The C#.NET ecosystem provides rich frameworks and libraries to help developers build applications efficiently. 1.ASP.NETCore is used to build high-performance web applications, 2.EntityFrameworkCore is used for database operations. By understanding the use and best practices of these tools, developers can improve the quality and performance of their applications.

Deploying C# .NET Applications to Azure/AWS: A Step-by-Step GuideDeploying C# .NET Applications to Azure/AWS: A Step-by-Step GuideApr 23, 2025 am 12:06 AM

How to deploy a C# .NET app to Azure or AWS? The answer is to use AzureAppService and AWSElasticBeanstalk. 1. On Azure, automate deployment using AzureAppService and AzurePipelines. 2. On AWS, use Amazon ElasticBeanstalk and AWSLambda to implement deployment and serverless compute.

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Tools

EditPlus Chinese cracked version

EditPlus Chinese cracked version

Small size, syntax highlighting, does not support code prompt function

MinGW - Minimalist GNU for Windows

MinGW - Minimalist GNU for Windows

This project is in the process of being migrated to osdn.net/projects/mingw, you can continue to follow us there. MinGW: A native Windows port of the GNU Compiler Collection (GCC), freely distributable import libraries and header files for building native Windows applications; includes extensions to the MSVC runtime to support C99 functionality. All MinGW software can run on 64-bit Windows platforms.

DVWA

DVWA

Damn Vulnerable Web App (DVWA) is a PHP/MySQL web application that is very vulnerable. Its main goals are to be an aid for security professionals to test their skills and tools in a legal environment, to help web developers better understand the process of securing web applications, and to help teachers/students teach/learn in a classroom environment Web application security. The goal of DVWA is to practice some of the most common web vulnerabilities through a simple and straightforward interface, with varying degrees of difficulty. Please note that this software

MantisBT

MantisBT

Mantis is an easy-to-deploy web-based defect tracking tool designed to aid in product defect tracking. It requires PHP, MySQL and a web server. Check out our demo and hosting services.

SecLists

SecLists

SecLists is the ultimate security tester's companion. It is a collection of various types of lists that are frequently used during security assessments, all in one place. SecLists helps make security testing more efficient and productive by conveniently providing all the lists a security tester might need. List types include usernames, passwords, URLs, fuzzing payloads, sensitive data patterns, web shells, and more. The tester can simply pull this repository onto a new test machine and he will have access to every type of list he needs.