Bảng băm (Hashtable) và từ điển (Dictionary) trong C# .NET – code bảng băm c++ – https://final-blade.com

Từ điển ( dictionary ) là loại kiểu tài liệu tập hợp đặc biệt quan trọng tàng trữ những cặp khóa – giá trị. Từ điển thường được sử dụng để tra cứu ( lookup ) trải qua việc ánh

Bạn đang xem: code bảng băm c++

Từ điển ( dictionary ) là loại kiểu tài liệu tập hợp đặc biệt quan trọng tàng trữ những cặp khóa – giá trị. Từ điển thường được sử dụng để tra cứu ( lookup ) trải qua việc ánh xạ khóa sang giá trị cần tìm .

Trong bài học này chúng ta sẽ xem xét phiên bản non-generic (Hashtable) và phiên bản generic (Dictionary) của kiểu từ điển trong C# .NET. Ngoài ra chúng ta cũng xem xét một loại từ điển đặc biệt, gọi là từ điển sắp xếp (SortedDictionary).

Giới thiệu về bảng băm
Bảng băm ( hash table, còn gọi là hash map ) là một kiểu tài liệu có vai trò rất quan trọng trong trong thực tiễn. Bảng băm được cho phép ánh xạ mỗi khóa ( key ) sang một giá trị ( value ) .
Mô hình hoạt động giải trí cơ bản của bảng băm được minh họa dưới đây :

Một trong những yêu cầu quan trọng nhất của bảng băm là khả năng tra cứu nhanh một giá trị (Value) dựa trên khóa (Key) của nó. Yêu cầu đặt ra là nó cần có độ phức tạp hằng số O(1).

Để đạt yêu cầu này người ta phải tạo ra các hàm băm (hash function). Nhiệm vụ của hàm băm là sinh ra chỉ số (index) tương ứng với khóa và đặt vào trong một danh sách gọi là Bucket. Chỉ số trong Bucket sẽ tương ứng với giá trị cần tra cứu.

Hàm băm có vai trò đặc biệt quan trọng quan trọng trong cấu trúc tài liệu này. Tối ưu nhất, hàm băm cần sinh ra chỉ số độc nhất cho mỗi khóa. Tuy nhiên, đôi lúc hàm băm vẫn hoàn toàn có thể sinh ra chỉ số trùng nhau ( dù khóa khác nhau ). Tình huống này được gọi là hash collision và cần phải giải quyết và xử lý .
Chủ đề thiết kế xây dựng bảng băm tương đối phức tạp và nằm ngoài khoanh vùng phạm vi của tài liệu này. Khi đó bạn phải tự thiết kế xây dựng và sử dụng hàm băm, giải quyết và xử lý hash collision, gán khóa vào bucket. Do đó, trong tài liệu này tất cả chúng ta chỉ xem xét việc sử dụng kiểu tài liệu sẵn có .
Với quy mô hoạt động giải trí như trên, khi cần tìm một giá trị dựa trên khóa, bạn không cần duyệt qua tổng thể những thành phần. Thay vào đó, hàm băm thuận tiện giúp xác lập được Bucket và lấy ra giá trị thiết yếu .
Do hiệu suất cao và không thay đổi, bảng năm được sử dụng rất thông dụng như trong mảng tích hợp ( associative array ), đánh chỉ số cơ sở tài liệu, những mạng lưới hệ thống đệm ( cache ) .

Class Hashtable trong C #

Hashtable là class cài đặt bảng băm (hash table, hash map) theo kiểu non-generic xây dựng sẵn trong C# .NET. Class này nằm trong namespace System.Collections.

Hãy cùng triển khai một ví dụ nhỏ để hiểu phương pháp thao tác của Hashtable class .
Để thuận tiện khi viết những chương trình nhỏ với giao diện dòng lệnh, trong những ví dụ sau sử dụng một bộ thư viện class tạo sẵn .

Bạn có thể tải file thư viện từ đường link sau:
https://1drv.ms/u/s!Ar_aj4rIJ2qGkZU4EYBdm4K3EptLTg?e=9ecAug
Sau khi tải về bạn tham chiếu chương trình tới file thư viện Framework.dll.

Bộ thư viện này tương hỗ bạn nhanh gọn kiến thiết xây dựng ứng dụng console với năng lực tiếp đón và giải quyết và xử lý lệnh / truy vấn từ người dùng + tham số của lệnh. Nó cũng có một số ít class tương hỗ hiển thị tài liệu trên console. Thêm vào đó, nếu ứng dụng phức tạp hơn, bạn hoàn toàn có thể sử dụng 1 số ít class tương hỗ để viết code theo quy mô MVC cho console .

Nếu quan tâm, bạn có thể đọc thêm loạt bài về cách xây dựng bộ thư viện hỗ trợ console này.

Tạo một project ConsoleApp (. NET Framework hoặc. NET Core ), cho tham chiếu tới file thư viện Framework. dll ( link tải ở trên ), và viết code cho Program. cs như sau :

using System;
using static System.Console;
using System.Collections;
using Framework;

namespace P01_Hashtable
{
    class Program
    {
        static readonly Hashtable _phoneBook = new Hashtable()
        {
            {"Trump", "0123.456.789" },
            {"Obama", "0987.654.321" },
            {"Putin", "0135.246.789" }
        };

        static void Main(string[] args)
        {
            var app = new Application()
            {
                Title = "PHONE BOOK by TUHOCICT.COM",
                Config = RegisterRoutes
            };

            app.Run();
        }

        private static void RegisterRoutes()
        {
            var router = Router.Instance;
            router.Register("add", AddNew, "Add new contact to the phone book:rnadd ? name=... & number =...");
            router.Register("list", ShowList, "Display number list:rnlist");
            router.Register("find", Find, "Lookup for number based on name:rnfind ? name = ...");
            router.Register("clear", Clear, "Clear the phone book. Be careful!rnclear ? confirm = yes");
        }

        private static void Clear(Parameter parameter)
        {
            var confirm = parameter["confirm"];
            if (confirm == "yes")
            {
                _phoneBook.Clear();
                WriteLine("The phone book has been cleared!");
            }
        }

        private static void Find(Parameter parameter)
        {
            var name = parameter["name"];
            if (!_phoneBook.ContainsKey(name))
            {
                ViewHelper.WriteLine("Contact not found. Try to add one", ConsoleColor.Yellow);
                return;
            }
            ViewHelper.WriteLine($"Contact found for {name}. The number is {_phoneBook[name]}", ConsoleColor.Cyan);
        }

        private static void ShowList(Parameter parameter)
        {
            if (_phoneBook.Count == 0)
            {
                ViewHelper.WriteLine("The phone book has no number", ConsoleColor.Yellow);
                return;
            }

            ViewHelper.WriteLine("### PHONE NUMBERS ###", ConsoleColor.Cyan);
            foreach (DictionaryEntry entry in _phoneBook)
            {
                WriteLine($" -> {entry.Key} : {entry.Value}");
            }
        }

        private static void AddNew(Parameter parameter)
        {
            string name = parameter["name"];
            string number = parameter["number"];

            if (_phoneBook.ContainsKey(name))
            {
                ViewHelper.WriteLine("Contact exists! The number will be replaced.", ConsoleColor.Yellow);
                _phoneBook[name] = number;
                return;
            }

            _phoneBook.Add(name, number);
            //_phoneBook[name] = number;            
        }
    }
}

Lưu ý những class Application, Router, Parameter, ViewHelper do thư viện Framework. dll cung cập. Chúng ta sử dụng bộ thư viện này để tránh phải viết code dài dòng cho giải quyết và xử lý nhập và thực thi lệnh từ giao diện console .
Kết quả chạy chương trình trên như sau :

Đây là một chương trình rất đơn thuần giúp bạn quản trị danh bạ điện thoại thông minh. Do danh bạ thường tổ chức triển khai ở những cặp tên ( khóa ) và số điện thoại thông minh ( giá trị ), Hashtable là cấu trúc tài liệu tự nhiên hơn cả để triển khai. Để đơn giản hóa, tất cả chúng ta dùng kiểu string cho cả khóa và giá trị .
Trong ví dụ trên tất cả chúng ta đã sử dụng những tính năng sau của class Hashtable .

Khai báo và khởi tạo Hashtable:

static readonly Hashtable _phoneBook = new Hashtable()
{
    {"Trump", "0123.456.789" },
    {"Obama", "0987.654.321" },
    {"Putin", "0135.246.789" }
};

Lưu ý cú pháp cung ứng giá trị để khởi tạo Hashtable : mỗi cặp khóa / giá trị đặt trong cặp dấu ngoặc nhọn { }, những cặp đặt cách nhau bằng dấu phẩy .

Thêm cặp khóa/giá trị mới:

_phoneBook.Add(name, number);
// hoặc
_phoneBook[name] = number;

Có hai cú pháp thêm cặp khóa/giá trị mới: sử dụng phương thức Add hoặc sử dụng indexer.

Nếu khóa đã sống sót, giá trị mới sẽ sửa chữa thay thế cho giá trị cũ .
Bạn không được phép sử dụng giá trị null cho phần khóa nhưng phần giá trị hoàn toàn có thể là null .

Truy xuất giá trị thông qua khóa:

Để truy xuất giá trị dựa trên khóa, bạn dùng phép toán indexer như sau :

_phoneBook[name]

Đây là truy xuất theo hai chiều, đọc giá trị ra và gán trị vào với khóa tương ứng .

Duyệt các cặp khóa/giá trị đang lưu trong Hashtable:

foreach (DictionaryEntry entry in _phoneBook)
{
    WriteLine($" -> {entry.Key} : {entry.Value}");
}

Bạn nên dùng vòng lặp foreach để duyệt Hashtable. Khi dùng foreach chú ý quan tâm không dùng từ khóa var cho biến tạm mà cần chỉ định rõ kiểu DictionaryEntry. Nếu không bạn sẽ không truy vấn được những phương pháp và thuộc tính của entry .

Đối với mỗi entry, hai thuộc tính quan trọng nhất là Key (khóa) và Value (giá trị tương ứng).

Kiểm tra khóa:

Bạn hoàn toàn có thể dùng phương pháp Contains hoặc ContainsKey để kiểm tra xem một khóa đã sống sót trong Hashtable hay chưa :

if (!_phoneBook.ContainsKey(name)) { ... }

Đếm số phần tử trong bảng Hashtable:

Bạn dùng thuộc tính Count để lấy số lượng thành phần hiện đang chứa trong bảng :

if (_phoneBook.Count == 0) { ... }

Xóa bỏ tất cả các phần tử:

Cuối cùng, nếu bạn có nhu yếu xóa bỏ toàn bộ những thành phần, bạn hoàn toàn có thể dùng phương pháp Clear :

_phoneBook.Clear();

Hashtable, do là một none-generic class, nó phải dùng kiểu object cho cả khóa và giá trị. Điều này hoàn toàn có thể dẫn đến quy trình boxing / unboxing cho những biến thuộc kiểu value type ( như int, book, char, DateTime, enum, struct, v.v. ) làm giảm hiệu suất của chương trình .
Do đó, bạn nên sử dụng class Dictionary sẽ ra mắt dưới đây .

Class Dictionary
Class Dictionary cũng là một thiết lập khác của bảng băm trong C #. NET. Khác biệt với Hashtable, Dictionary là một generic class trong namespace System. Collection. Generics .
Do là một generic class, bạn hoàn toàn có thể chỉ định kiểu cho khóa và giá trị, tận dụng được năng lực kiểm tra kiểu của C # compiler, đồng thời tránh việc boxing / unboxing biến thuộc những kiểu value type .
Cách sử dụng của Dictionary cơ bản là giống như Hashtable. Chúng ta cùng triển khai lại ví dụ trên nhưng sử dụng Dictionary .

using System;
using static System.Console;
using Framework;
using System.Collections.Generic;

namespace P02_Dictionary
{
    class Program
    {
        static readonly Dictionary _phoneBook = new Dictionary()
        {
            {"Trump", "0123.456.789" },
            {"Obama", "0987.654.321" },
            {"Putin", "0135.246.789" }
        };

        static void Main(string[] args)
        {
            var app = new Application()
            {
                Title = "PHONE BOOK by TUHOCICT.COM",
                Config = RegisterRoutes
            };

            app.Run();
        }

        private static void RegisterRoutes()
        {
            var router = Router.Instance;
            router.Register("add", AddNew, "Add new contact to the phone book:rnadd ? name=... & number =...");
            router.Register("list", ShowList, "Display number list:rnlist");
            router.Register("find", Find, "Lookup for number based on name:rnfind ? name = ...");
            router.Register("clear", Clear, "Clear the phone book. Be careful!rnclear ? confirm = yes");
        }

        private static void Clear(Parameter parameter)
        {
            var confirm = parameter["confirm"];
            if (confirm == "yes")
            {
                _phoneBook.Clear();
                WriteLine("The phone book has been cleared!");
            }
        }

        private static void Find(Parameter parameter)
        {
            var name = parameter["name"];
            if (!_phoneBook.ContainsKey(name))
            {
                ViewHelper.WriteLine("Contact not found. Try to add one", ConsoleColor.Yellow);
                return;
            }
            ViewHelper.WriteLine($"Contact found for {name}. The number is {_phoneBook[name]}", ConsoleColor.Cyan);
        }

        private static void ShowList(Parameter parameter)
        {
            if (_phoneBook.Count == 0)
            {
                ViewHelper.WriteLine("The phone book has no number", ConsoleColor.Yellow);
                return;
            }

            ViewHelper.WriteLine("### PHONE NUMBERS ###", ConsoleColor.Cyan);
            foreach (KeyValuePair entry in _phoneBook)
            {
                WriteLine($" -> {entry.Key} : {entry.Value}");
            }
        }

        private static void AddNew(Parameter parameter)
        {
            string name = parameter["name"];
            string number = parameter["number"];

            if (_phoneBook.ContainsKey(name))
            {
                ViewHelper.WriteLine("Contact exists! The number will be replaced.", ConsoleColor.Yellow);
                _phoneBook[name] = number;
                return;
            }

            _phoneBook.Add(name, number);
            //_phoneBook[name] = number;            
        }
    }
}

Bạn hoàn toàn có thể thấy, những thao tác thao tác với Dictionary về cơ bản là giống như Hashtable, ngoại trừ :

Khai báo và khởi tạo Dictionary:

static readonly Dictionary _phoneBook = new Dictionary()
{
    {"Trump", "0123.456.789" },
    {"Obama", "0987.654.321" },
    {"Putin", "0135.246.789" }
};

Khi khai báo object kiểu Dictionary, bạn phải chỉ định rõ kiểu của khóa và giá trị. Trong ví dụ trên, khóa và giá trị đều có kiểu là string .
Tương tự, khi khởi tạo những thành phần, bạn phải phân phối giá trị theo đúng kiểu đã khai báo so với phần khóa và phần giá trị trong cặp { } .

Duyệt các phần tử của Dictionary:

Mỗi cặp khóa/giá trị của Dictionary thuộc kiểu KeyValuePair. Do đó bạn cần chỉ định rõ tên kiểu đối với biến iterator:

foreach (KeyValuePair entry in _phoneBook)
{
    WriteLine($" -> {entry.Key} : {entry.Value}");
}

Các phương thức TryGet, TryAdd:

Đây là hai phương pháp của Dictionary giúp bạn thử lấy giá trị theo khóa hoặc thử gán giá trị cho một khóa. Nó giúp bạn tránh phải triển khai kiểm tra xem khóa đó có sống sót hay không .
Thêm vào đó, kiểu tài liệu của phần giá trị được xác lập rõ ràng, bạn không cần cast về kiểu đích nữa. C # Compiler cũng giúp bạn kiểm tra kiểu của giá trị gán cho phần khóa và phân giá trị .
Dưới đây là một ví dụ khác minh họa hoạt động giải trí của Dictionary với những kiểu tài liệu phức tạp hơn :

using System;
using System.Collections.Generic;
using Framework;

namespace P03_Dictionary2
{
    class Program
    {
        static void Main(string[] args)
        {
            var app = new Application()
            {
                Title = "STUDENT CHECKIN",
                Config = RegisterQueries
            };
            app.Run();
        }

        private static void RegisterQueries()
        {
            var router = Router.Instance;
            router.Register("check", Check, "Check if the given Id is from a real Hogwarts studentrnsyntax: check ? id = ...");
        }

        private static void Check(Parameter parameter)
        {
            var id = parameter["id"].To();
            if (DataAccess.Students.TryGetValue(id, out Student s))
            {
                ViewHelper.WriteLine($"Welcome, {s.FirstName} {s.LastName} from {s.Group}!", ConsoleColor.Green);
            }
            else
            {
                ViewHelper.WriteLine($"There's no student with Id {id} in Hogwarts. Are you lost?", ConsoleColor.Yellow);
            }
        }
    }

    class DataAccess
    {
        public static Dictionary Students { get; } = new Dictionary
        {
            {10000, new Student{FirstName = "Harry", LastName = "Potter", Group = "Gryffindor"} },
            {10002, new Student{FirstName = "Hermione", LastName = "Granger", Group = "Gryffindor"} },
            {10003, new Student{FirstName = "Neville", LastName = "Longbottom", Group = "Gryffindor"} },
            {10004, new Student{FirstName = "Ronald", LastName = "Weasley", Group = "Gryffindor"} },
            {20001, new Student{FirstName = "Draco", LastName = "Malfoy", Group = "Slytherin"} },
            {20002, new Student{FirstName = "Severus", LastName = "Snape", Group = "Slytherin"} },
            {20003, new Student{FirstName = "Tom", LastName = "Riddle", Group = "Slytherin"} },
            {30001, new Student{FirstName = "Luna", LastName = "Lovegood", Group = "Ravenclaw"} },
            {40001, new Student{FirstName = "Cedric", LastName = "Diggory", Group = "Hufflepuff"} },
        };
    }

    class Student
    {
        public string FirstName { get; set; }
        public string LastName { get; set; }
        public string Group { get; set; }
    }
}

Đây chỉ là một ví dụ nhỏ vui để minh họa năng lực tra cứu ( lookup ) của Dictionary trong C # .

SortedDictionary class
Hai class setup bảng băm Hashtable và Dictionary đều không duy trì thứ tự của những thành phần ( đúng mực hơn là sắp xếp theo khóa ). Trong trường hợp bạn cần sắp xếp những thành phần theo khóa của nó, bạn hoàn toàn có thể sử dụng một thiết lập khác : class SortedDictionary .

SortedDictionary cũng là một generic class và nằm trong namespace System.Collections.Generic.

Về cách sử dụng, SortedDictionary trọn vẹn giống hệt như Dictionary. Khác biệt duy nhất là những thành phần của nó được tự động hóa sắp xếp lại theo khóa khi bạn thêm thành phần mới hoặc xóa thành phần .
Một điều cần quan tâm nữa là SortedDictionary có độ phức tạp O ( log n ) khi truy xuất / thêm / xóa thành phần, thay vì O ( 1 ) của Dictionary / Hashtable .
Hãy cùng thực thi một ví dụ nhỏ. Trong ví dụ này tất cả chúng ta sẽ thiết kế xây dựng một “ từ điển bách khoa ” siêu mini để minh họa cách sử dụng SortedList. Kiểu dữ liệu này tương thích hơn cả vì nó vừa được cho phép tra cứu, đồng thời cũng sắp xếp từ khóa .

using System;
using Framework;
using System.Collections.Generic;
using System.Linq;

namespace P04_Encyclopedia
{
    class Program
    {
        static readonly Encyclopedia _encyclopedia = new Encyclopedia();

        static void Main(string[] args)
        {
            var app = new Application
            {
                Title = "CITY ENCYCLOPEDIA",
                Prompt = "# Search >> ",
                Config = Register,
                Color = ConsoleColor.Magenta
            };

            app.Run();
        }

        private static void Register()
        {
            var router = Router.Instance;
            router.Register("article", SearchForArticle, "Search for city articles.rnSyntax: article ? topic = ... ");
            router.Register("all articles", ShowAllArticles, "Search for country articles.rnSyntax: all articles");
        }

        private static void ShowAllArticles(Parameter parameter)
        {
            foreach (KeyValuePair a in _encyclopedia.Articles)
            {
                ViewHelper.Write($"Keyword: {a.Key}. ", ConsoleColor.Green);
                ViewHelper.WriteLine($"Title: {a.Value.Title}");
            }
        }

        private static void SearchForArticle(Parameter parameter)
        {
            var topic = parameter["topic"];
            var a = _encyclopedia.GetArticle(topic);
            if (a != null)
            {
                ViewHelper.WriteLine($"### {a.Title} ###", ConsoleColor.Green);
                ViewHelper.WriteLine(a.Content);
                return;
            }
            ViewHelper.WriteLine($"The topic '{topic}' not found!", ConsoleColor.Yellow);
        }
    }

    class Encyclopedia
    {
        public SortedDictionary Articles { get; set; } = new SortedDictionary
        {
            {"LONDON", new Article{Title = "London", Content = "The capital city of the United Kingdoms"} },
            {"MOSCOW", new Article{Title = "Moscow", Content = "The capital city of the Russian Federation"} },
            {"WASHINGTON", new Article{Title = "Washington", Content = "The capital city of the United States of America"} },
            {"PARIS", new Article{Title = "Paris", Content = "The capital city of the Republic of France"} },
            {"BEIJING", new Article{Title = "Beijing", Content = "The capital city of the People Republic of China"} },
            {"RUSSIA", new Article{Title = "Russian Federation", Content = "The largest country in the world"} },
            {"USA", new Article{Title = "United States of America", Content = "The most powerful country in the world"} },
            {"AUSTRALIA", new Article{Title = "Commonwealth of Australia", Content = "The largest country in the southern hemisphere"} },
            {"VATICAN", new Article{Title = "Vatican City", Content = "The smallest country in the world" } },
        };

        public Article GetArticle(string topic)
        {
            if (Articles.TryGetValue(topic.Trim().ToUpper(), out Article article))
            {
                return article;
            }
            return null;
        }
    }

    class Article
    {
        public string Title { get; set; }
        public string Content { get; set; }
    }
}

Như bạn đã thấy trong ví dụ trên, sử dụng SortedDictionary không có gì độc lạ với Dictionary, ngoại trừ toàn bộ những thành phần được tự động hóa sắp xếp theo khóa .

Kết luận

Trong bài học này chúng ta đã xem xét qua cách sử dụng hai class cài đặt bảng băm trong C#: Hashtable, Dictionary, SortedDictionary. Nhìn chung, các class này đã che hết những phức tạp trong quá cài trình cài đặt bảng băm. Nó giúp bạn dễ dàng sử dụng trong các chương trình mà không cần tự mình thực thi lại các thuật toán phức tạp bên trong.

Cách sử dụng những class này khá đơn thuần và tương tự như nhau .
Cũng nên chú ý quan tâm rằng, ứng dụng thực tiễn của loại cấu trúc tài liệu này không giống như những ví dụ tất cả chúng ta thực thi ở trên. Các ví dụ này chỉ mang đặc thù minh họa cho cách sử dụng của những class. NET thiết kế xây dựng sẵn .

+ Nếu bạn thấy site hữu ích, trước khi rời đi hãy giúp đỡ site bằng một hành động nhỏ để site có thể phát triển và phục vụ bạn tốt hơn.
+ Nếu bạn thấy bài viết hữu ích, hãy giúp chia sẻ tới mọi người.
+ Nếu có thắc mắc hoặc cần trao đổi thêm, mời bạn viết trong phần thảo luận cuối trang.
Cảm ơn bạn!

Source: https://final-blade.com
Category : Kiến thức Internet