Từ điển (dictionary) là loại kiểu dữ liệu tập hợp đặc biệt lưu trữ các cặp khóa – giá trị. Từ điển thường được sử dụng để tra cứu (lookup) thông 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 dữ liệu có vai trò rất quan trọng trong thực tế. Bảng băm cho phép ánh xạ mỗi khóa (key) sang một giá trị (value).
Mô hình hoạt động 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 trong cấu trúc dữ 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 khi hàm băm vẫ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 xử lý.
Chủ đề xây dựng bảng băm tương đối phức tạp và nằm ngoài phạm vi của tài liệu này. Khi đó bạn phải tự xây dựng và sử dụng hàm băm, xử lý hash collision, gán khóa vào bucket. Do đó, trong tài liệu này chúng ta chỉ xem xét việc sử dụng kiểu dữ liệu sẵn có.
Với mô hình hoạt động 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ất cả các phần tử. Thay vào đó, hàm băm dễ dàng giúp xác định được Bucket và lấy ra giá trị cần thiết.
Do hiệu suất cao và ổn định, bảng năm được sử dụng rất phổ biến như trong mảng kết hợp (associative array), đánh chỉ số cơ sở dữ liệu, các 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 thực hiện một ví dụ nhỏ để hiểu cách thức làm việc của Hashtable class.
Để tiện lợi khi viết các chương trình nhỏ với giao diện dòng lệnh, trong các 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 hỗ trợ bạn nhanh chóng xây dựng ứng dụng console với khả năng tiếp nhận 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ố class hỗ trợ hiển thị dữ liệu trên console. Thêm vào đó, nếu ứng dụng phức tạp hơn, bạn có thể sử dụng một số class hỗ trợ để viết code theo mô hình 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.
[wpdm_package id=’11835′]
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:\r\nadd ? name=... & number =...");
router.Register("list", ShowList, "Display number list:\r\nlist");
router.Register("find", Find, "Lookup for number based on name:\r\nfind ? name = ...");
router.Register("clear", Clear, "Clear the phone book. Be careful!\r\nclear ? 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 ý các 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 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 giản giúp bạn quản lý danh bạ điện thoại. Do danh bạ thường tổ chức ở các cặp tên (khóa) và số điện thoại (giá trị), Hashtable là cấu trúc dữ liệu tự nhiên hơn cả để thực hiện. Để đơn giản hóa, chúng ta dùng kiểu string cho cả khóa và giá trị.
Trong ví dụ trên chúng ta đã sử dụng các 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 cấp 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 {}, các 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 đã tồn tại, giá trị mới sẽ 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ị 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 lưu ý 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 cập được các phương thức 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 có thể dùng phương thức Contains hoặc ContainsKey để kiểm tra xem một khóa đã tồn tại 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 phần tử 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 cầu xóa bỏ tất cả các phần tử, bạn có thể dùng phương thức 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 có thể dẫn đến quá 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ẽ giới thiệu dưới đây.
Class Dictionary
Class Dictionary cũng là một cài đặt 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 có thể chỉ định kiểu cho khóa và giá trị, tận dụng được khả năng kiểm tra kiểu của C# compiler, đồng thời tránh việc boxing/unboxing biến thuộc các 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 thực hiện 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<string, string> _phoneBook = new Dictionary<string, string>()
{
{"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:\r\nadd ? name=... & number =...");
router.Register("list", ShowList, "Display number list:\r\nlist");
router.Register("find", Find, "Lookup for number based on name:\r\nfind ? name = ...");
router.Register("clear", Clear, "Clear the phone book. Be careful!\r\nclear ? 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<string, string> 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 có thể thấy, các thao tác làm việ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<string, string> _phoneBook = new Dictionary<string, string>()
{
{"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 các phần tử, bạn phải cung cấp giá trị theo đúng kiểu đã khai báo đối 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<TKey, TValue>. Do đó bạn cần chỉ định rõ tên kiểu đối với biến iterator:
foreach (KeyValuePair<string, string> entry in _phoneBook)
{
WriteLine($" -> {entry.Key} : {entry.Value}");
}Các phương thức TryGet, TryAdd:
Đây là hai phương thức 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 thực hiện kiểm tra xem khóa đó có tồn tại hay không.
Thêm vào đó, kiểu dữ liệu của phần giá trị được xác định 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 của Dictionary với các kiểu dữ 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 student\r\nsyntax: check ? id = ...");
}
private static void Check(Parameter parameter)
{
var id = parameter["id"].To<int>();
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<int, Student> Students { get; } = new Dictionary<int, Student>
{
{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 khả năng tra cứu (lookup) của Dictionary trong C#.
SortedDictionary class
Hai class cài đặt bảng băm Hashtable và Dictionary đều không duy trì thứ tự của các phần tử (chính xác hơn là sắp xếp theo khóa). Trong trường hợp bạn cần sắp xếp các phần tử theo khóa của nó, bạn có thể sử dụng một cài đặt 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 hoàn toàn giống hệt như Dictionary. Khác biệt duy nhất là các phần tử của nó được tự động sắp xếp lại theo khóa khi bạn thêm phần tử mới hoặc xóa phần tử.
Một điều cần lưu ý nữa là SortedDictionary có độ phức tạp O(log n) khi truy xuất/thêm/xóa phần tử, thay vì O(1) của Dictionary/Hashtable.
Hãy cùng thực hiện một ví dụ nhỏ. Trong ví dụ này chúng ta sẽ 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 phù hợp hơn cả vì nó vừa 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.\r\nSyntax: article ? topic = ... ");
router.Register("all articles", ShowAllArticles, "Search for country articles.\r\nSyntax: all articles");
}
private static void ShowAllArticles(Parameter parameter)
{
foreach (KeyValuePair<string, Article> 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<string, Article> Articles { get; set; } = new SortedDictionary<string, Article>
{
{"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ì khác biệt với Dictionary, ngoại trừ tất cả các phần tử được tự động 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 các class này khá đơn giản và tương tự nhau.
Cũng nên lưu ý rằng, ứng dụng thực tế của loại cấu trúc dữ liệu này không giống như những ví dụ chúng ta thực hiện ở trên. Các ví dụ này chỉ mang tính chất minh họa cho cách sử dụng của các class .NET xây dựng sẵn.
[wpdm_package id=’11815′]
+ 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!
Vẫn chưa có bài Tree hả ad?.. em tìm không thấy nơi.
Rất xin lỗi bạn. Thầy phụ trách bài giảng về thuật toán hiện đang có chút việc cá nhân nên tạm thời chưa viết được bài mới.