Kiểu từ điển
Để tìm thấy giá trị trong từ điển chúng ta hãy tưởng tượng rằng chúng ta muốn giữ một danh sách các thủ phủ của bang. Một hướng tiếp cận là đặt chúng vào trong một mảng theo thứ tự anphabe như sau: string[] stateCapitals = new string[50]; ...
Để tìm thấy giá trị trong từ điển chúng ta hãy tưởng tượng rằng chúng ta muốn giữ một danh sách các thủ phủ của bang. Một hướng tiếp cận là đặt chúng vào trong một mảng theo thứ tự anphabe như sau:
string[] stateCapitals = new string[50];
Mảng stateCapital sẽ nắm giữ 50 thủ phủ bang. Mỗi thủ phủ được truy cập như một khoảng dời (offset) trong mảng.
Để truy cập thủ phủ của bang Arkansas, chúng ta cần phải biết bang Arkansas nằm ở vị trí thứ tư trong thứ tự alphabe danh sách các bang, nên ta có thể truy cập như sau:
string capitalOfArkansas = stateCapitals[3];
Tuy nhiên, thật không thuận tiện khi khi truy cập các thủ phủ của các bang thông qua cấu trúc mảng như vậy. Giả sử nếu chúng ta muốn truy cập thủ phủ của bang Massachusett, không phải dễ dàng xác định rằng thứ tự của bang là thứ 21 theo alphabe.
Một cách thuận tiện hơn là lưu trữ thủ phủ theo tên của bang. Một từ điển cho phép chúng ta lưu trữ một giá trị (trong trường hợp này là thủ phủ) và với một khóa truy cập (là tên của bang). Kiểu dữ liệu từ điển trong .NET Framework có thể kết hợp bất cứ kiểu khóa nào như kiểu chuỗi, số nguyên, đối tượng...với bất cứ kiểu giá trị nào (chuỗi, số nguyên, kiểu đối tượng).
Thuộc tính quan trọng của một từ điển tốt là dễ thêm giá trị mới vào, và nhanh chóng truy cập đến giá trị. Một vài từ điển thì nhanh hơn về thời gian thêm một giá trị mới vào, một số khác thì tối ưu cho việc truy cập. Một trong minh họa cho kiểu từ điển là kiểu dữ liệu hashtable hay còn gọi là bảng băm.
Hashtable là một kiểu từ điển được tối ưu cho việc truy cập được nhanh. Một số các phương thức chính và các thuộc tính của kiểu dữ liệu Hashtable được trình bày trong bảng dưới.
| Phương thức- thuộc tính | Mục đích |
| Synchronized() | Phương thức static trả về một Hashtable wrapperđược thread-safe. |
| Count | Thuộc tính trả về số thành phần trong hashtable |
| IsReadOnly | Thuộc tính xác định hashtable là chỉ đọc |
| IsSynchronized | Thuộc tính xác định hashtable được đồng bộ |
| SyncRoot | Thuộc tính trả về đối tượng có thể được sử dụng đểđồng bộ truy cập Hastable. |
| Keys | Thuộc tính trả về một ICollection chứa những khóa trong hashtable. |
| Values | Thuộc tính trả về một ICollection chứa những giátrị trong hashtable. |
| Add() | Thêm một thành phần mới với khóa và giá trị xácđịnh. |
| Clear() | Xóa tất cả đối tượng trong hashtable. |
| Item() | Chỉ mục cho hastable |
| Clone() | Tạo ra một bản sao |
| Contains() | Xác định xem một thành phần có trong hashtable. |
| ContainsKey() | Xác định xem hashtable có chứa một khóa xácđịnh |
| CopyTo() | Sao chép những thành phần của hashtable đếnmảng một chiều đã tồn tại |
| GetEnumerator() | Trả về một enumerator cho hashtable. |
| GetObjectData() | Thực thi ISerializable và trả về dữ liệu cần thiết đểlưu trữ. |
| OnDeserialization | Thực thi ISerializable và phát sinh sự kiệndeserialization khi hoàn thành. |
| Remove() | Xóa một thành phần với khóa xác định. |
Trong một Hashtable, mỗi giá trị được lưu trữ trong một vùng. Mỗi vùng được đánh số tương tự như là từng offset trong mảng. Do khóa có thể không phải là số nguyên, nên phải chuyển các khóa thành các khóa số để ánh xạ đến vùng giá trị được đánh số. Mỗi khóa phải cung cấp phương thức GetHashCode() để nhận giá trị mã hóa thành số của nó. Chúng ta nhớ rằng mọi thứ trong C# đều được dẫn xuất từ lớp object. Lớp object cung cấp một phương thức ảo là GetHashCode(), cho phép các lớp dẫn xuất tự do kế thừa hay viết lại. Việc thực thi thông thường của phương thức GetHashCode() đối với chuỗi thì đơn giản bằng cách cộng các giá trị Unicode của từng ký tự lại rồi sau đó sử dụng toán tử chia lấy dư để nhận lại một giá trị từ 0 đến số vùng được phân của hashtable. Ta không cần phải viết lại phương thức này với kiểu chuỗi.
Khi chúng ta thêm giá trị vào Hashtable thì Hashtable sẽ gọi phương thức GetHashCode() cho mỗi giá trị mà chúng ta cung cấp. Phương thức này trả về một số nguyên, xác định vùng mà giá trị được lưu trữ trong hashtable.Dĩ nhiên là có thể nhiều giá trị nhận chung một khóa tức là cùng một vùng trong hashtable, điều này gọi là sự xung đột. Có một vài cách để giải quyết sự xung đột này. Trong đó cách chung nhất và được hỗ trợ bởi CLR là cho mỗi vùng duy trì một danh sách có thứ tự các giá trị. Khi chúng ta truy cập một giá trị trong hashtable, chúng ta cung cấp một khóa. Một lần nữa Hashtable gọi phương thức GetHashCode() trên khóa và sử dụng giá trị trả về để tìm vùng tương ứng. Nếu chỉ có một giá trị thì nó sẽ trả về, nếu có nhiều hơn hai giá trị thì việc tìm kiếm nhị phân sẽ được thực hiện trên những nội dung của vùng đó. Bởi vì có một vài giá trị nên việc tìm kiếm này thực hiện thông thường là rất nhanh.
Khóa trong Hashtable có thể là kiểu dữ liệu nguyên thủy hay là các thể hiện của các kiểu dữ liệu do người dùng định nghĩa (các lớp cho người lập trình tạo ra). Những đối tượng được sử dụng làm khóa trong hashtable phải thực thi GetHashCode() và Equals(). Trong hầu hết trường hợp, chúng ta có thể sử dụng kế thừa từ Object.
Hashtable là một từ điển ví nó thực thi giao diện IDictionary. IDictionary cung cấp một thuộc tính public là Item. Thuộc tính Item truy cập một giá trị thông qua một khóa xác định. Trong ngôn ngữ C# thuộc tính Item được khai báo như sau:
object this[object key]
{ get; set;}
Thuộc tính Item được thực thi trong ngôn ngữ C# với toán tử chỉ mục ([]). Do vậy chúng ta có thể truy cập những item trong bất cứ đối tượng từ điển bằng cú pháp giống như truy cập mảng.
Ví dụ sau minh họa việc thêm một item vào trong bảng Hashtable và sau đó truy cập lại chúng thông qua thuộc tính Item.
thuộc tính Item tương như như toán tử offset.
-----------------------------------------------------------------------------
namespace Programming_CSharp
{
using System;
using System.Collections;
public class Tester
{
static void Main()
{
// tạo và khởi tạo hashtable
Hashtable hashTable = new Hashtable();
hashTable.Add("00440123","Ngoc Thao");
hashTable.Add("00123001","My Tien");
hashTable.Add("00330124","Thanh Tung");
// truy cập qua thuộc tính Item
Console.WriteLine("myHashtable["00440123"]: {0}", hashTable["00440123"]);
}
}
}
-----------------------------------------------------------------------------
Kết quả:
hashTable[“00440123”]: Ngoc Thao
-----------------------------------------------------------------------------
Ví dụ trên bắt đầu bằng việc tạo một bảng Hashtable mới, sử dụng các giá trị mặc định của dung lượng, phương thức tạo mã băm và phương tức so sánh. Tiếp sau là việc thêm 3 bộ giá trị vào theo thứ tự khóa/giá trị. Sau khi các item đã được thêm vào chúng ta có thể lấy giá trị thông qua khóa với cách thức dùng toán tử offset.
Các kiểu từ cung cấp thêm hai thuộc tính là thuộc tính Keys, và thuộc tính Values. Trong đó Keys truy cập đối tượng ICollection với tất cả những khóa trong Hashtable, và Values truy cập đối tượng ICollection với tất cả giá trị. Ví dụ minh họa như sau.
Tập khóa và tập giá trị.
-----------------------------------------------------------------------------
namespace Progrmming_CSharp
{
using System;
using System.Collections;
public class Tester
{
static void Main()
{
// tạo và khởi tạo hashtable
Hashtable hashTable = new Hashtable();
hashTable.Add("00440123","Ngoc Thao");
hashTable.Add("00123001","My Tien");
hashTable.Add("00330124","Thanh Tung");
// nhận tập khóa
ICollection keys = hashTable.Keys;
// nhập tập giá trị
ICollection values = hashTable.Values;
// xuất tập khóa
foreach( string s in keys)
{
Console.WriteLine("{0}", s);
}
// xuất tập giá trị
foreach( string s in values)
{
Console.WriteLine("{0}", s);
}
}
}
}
-----------------------------------------------------------------------------
Kết quả:
00123001
00440123
00330124
My Tien
Ngoc Thao
Thanh Tung
-----------------------------------------------------------------------------
Mặc dù thứ tự của keys không được đảm bảo theo thứ tự nhưng chúng đảm bảo rằng cùng với thứ tự đưa ra của giá trị. Như chúng ta thấy trên khóa 00123001 tương ứng với My Tien,...
Những đối tượng IDictionary cũng hỗ trợ vòng lặp foreach bằng việc thực thi phương thức GetEnumerator(), phương thức này trả về một IDictionaryEnumerator. IDictionaryEnumerator được sử dụng để liệt kê bất cứ đối tượng IDictionary nào. Nó cung cấp thuộc tính để truy cập cả khóa và giá trị cho mỗi thành phần trong từ điển. Ta có ví dụ minh họa như sau:
Sử dụng giao diện IDictionaryEnumerator.
-----------------------------------------------------------------------------
namespace Progrmming_CSharp
{
using System;
using System.Collections;
public class Tester
{
static void Main()
{
// tạo và khởi tạo hashtable
Hashtable hashTable = new Hashtable();
hashTable.Add("00440123","Ngoc Thao");
hashTable.Add("00123001","My Tien");
hashTable.Add("00330124","Thanh Tung");
Console.WriteLine("hashTable");
Console.WriteLine("Count: {0}",hashTable.Count);
Console.WriteLine("Keys and Values:");
Print( hashTable );
}
public static void Print(Hashtable table)
{
IDictionaryEnumerator enumerator = table.GetEnumerator();
while ( enumerator.MoveNext() )
{
Console.WriteLine(" {0}: {1}", enumerator.Key, enumerator.Value);
}
Console.WriteLine();
}
}
}
-----------------------------------------------------------------------------
Kết quả: hashTableg Count: 3
Keys and Values:
00123001: My Tien
00440123: Ngoc Thao
00330124: Thanh Tung
-----------------------------------------------------------------------------
Câu hỏi và trả lời
Điều phân biệt giữa mảng và các thành phần bên trong một mảng?
Mảng là kiểu dữ liệu tham chiếu, còn các thành phần bên trong mảng được cấp phát dựa theo kiểu dữ liệu của chúng. Do vậy một mảng của kiểu dữ liệu tham chiếu sẽ không chứa giá trị gì cả mà chỉ tham chiếu đến những thành phần được tạo ra trên heap.
Một lớp có bộ chỉ mục khác một mảng như thế nào?
Hoàn toàn khác nhau, một mảng chỉ đơn thuần là một đối tượng tham chiếu đến những đối tượng khác cùng kiểu dữ liệu. Trong khi một lớp có bộ chỉ mục thì nó chứa một mảng các giá trị nào đó, và cho phép bên ngoài truy cập mảng này thông qua bộ chỉ mục. Một lớp như vậy không chỉ có một mảng đơn thuần mà còn có những thuộc tính khác, các phương thức...Nói chung là nếu ta chỉ cần thao tác đơn thuần trên từng phần riên lẻ của một mảng thì nên dùng mảng. Còn nếu chúng ta cần thực hiện một số chức năng nào đó có liên quan tới một mảng thì ta có thể xây dựng một lớp có chứa một mảng và hỗ trợ bộ chỉ mục.
Giao diện tập hợp là gì? Có phải .NET cung cấp một số giao diện chuẩn hay không?
Giao diện tập hợp cũng là một giao diện nhưng nó chỉ đưa ra các quy định thao tác trên tập hợp như: so sánh, liệt kê trên tập hợp, tạo các tập hợp... NET cung cấp một số giao diện cho tập hợp như: IEnumerable, ICollection, IComparer, IList....
Câu hỏi thêm
Từ khoá params được sử dụng làm gì?
Ý nghĩa của lệnh lặp foreach? Lệnh này được sử dụng với kiểu dữ liệu nào?
Có mấy kiểu mảng đa chiều trong ngôn ngữ C#. Hãy cho biết từng loại và khi nào thì sử dụng từng loại cho thích hợp.
Cách tạo ra mảng đa chiều không cùng kích thước?
Hãy cho biết sự khác nhau giữa hai cách gọi Arr[i][j] và Arr[i, j]?
Có thể dùng lệnh foreach để xuất ra tất cả các thành phần của mảng đa chiều không cùng kích thước hay không? Nếu được thì phải làm như thế nào?
Kiểu dữ liệu nào có thể làm chỉ mục trong bộ chỉ mục của một lớp? Câuhỏi 8: Làm thế nào để biết kích thước của một mảng?
Liệt kê những giao diện tập hợp mà .NET cung cấp? Cho biết ý nghĩa của từng giao diện?
Có cách nào tạo một mảng mà không cần khai báo trước kích thước của mảng?Và trong quá trình thực hiện trên mảng chúng ta có thể tăng động kích thước của mảng hay không?
Nếu mảng có 31 phần tử thì dung lượng của đối tượng ArrayList là bao nhiêu? Trường hợp có 33 phần tử?
Hàng đợi là gì? Chúng được sắp xếp theo kiểu thứ tự nào? Ứng dụng của hàng đợi ?
Ngăn xếp là gì? Chúng được sắp xếp theo kiểu thứ tự nào? Ứng dụng của ngăn xếp?
Phương thức Peek() trong hàng đợi và ngăn xếp có ý nghĩa gì?
Kiểu dữ liệu nào cho phép truy cập một giá trị thông qua khóa của nó? Lớp nào trong .NET hỗ trợ kiểu dữ liệu này?
Cách lấy tập giá trị trong một đối tượng Hashtable? Câuhỏi 17: Cách lấy tập khóa trong một đối tượng Hastable?
Khóa có phải là duy nhất trong một Hastable hay không?
Nếu hai vùng có chung một khóa thì chúng được tìm kiếm theo kiểu nào? Và tốc độ tìm kiếm?
Hashtable thực thi các giao diện tập hợp nào?
Phương thức nào thực hiện việc tạo các khoá trong một Hashtable?
Bài tập
Viết một chương trình tạo một mảng một chiều nguyên chứa giá trị ngẫu nhiên. Sắp xếp các thành phần trong mảng theo thứ tự tăng dần và hiển thị kết quả. Làm tương tự với trường hợp sắp xếp mảng theo thứ tự giảm dần.
Viết một chương trình tạo một mảng một chiều nguyên chứa giá trị ngẫu nhiên. Sắp xếp chúng theo thứ tự số âm thì tăng còn số dương thì giảm dần. Hiển thị kết quả ra màn hình.
Viết một chương trình tìm số lớn nhất và nhỏ nhất trong mảng hai chiều có kích thước cố định. Các thành phần của mảng được phát sinh ngẫu nhiên.
Viết chương trình cộng hai ma trận nxm, tức là mảng hai chiều có kích thước n dòng, m cột. Các giá trị của hai mảng phát sinh ngẫu nhiên, cho biết kết quả cộng hai ma trận?
Viết chương trình cho phép người dùng nhập vào một ma trận nxm, sao đó tìm kiếm một giá trị nào đó theo yêu cầu người dùng, kết quả của việc tìm kiếm là giá trị và thứ tự của giá trị tìm được trong ma trận.
Viết chương trình tạo một mảng hai chiều không cùng kích thước. Cố định số dòng của mảng là 5, còn từng dòng có kích thước bằng giá trị của dòng, tứ là dòng thứ nhất có kích thước 1 (tức là có 1 cột), dòng thứ hai có kích thước là 2 (tức là 2 cột).... Các giá trị phát sinh ngẫu nhiên. Hãy xuất kết quả của ma trận theo kiểu sau:
a[i][j] = <giá trị aij>
...
Việc xuất kết quả của ma trận trên có thể thực hiện bằng vòng lặp foreach được không? Nếu được thì hãy viết đoạn chương trình xuất ra kết quả?
Viết chương trình tạo ra một mảng lưu trữ 30 điểm số của học sinh. Tính trung bình điểm của tất cả học sinh. Xuất kết quả từng điểm và điểm trung bình.
Viết một chương trình tạo ra một lớp tên là LopHoc, trong đó có khai báo bộ chỉ mục chỉ đến tên của từng học viên trong lớp. Cho phép một lớp có tối đa 30 học viên. Tạo chương trình minh họa cho phép người dùng nhập vào tên của từng học viên. Xuất kết quả danh sánh học viên của lớp thông qua bộ chỉ mục.
Viết chương trình sử dụng ArrayList để tạo một mảng. Chương trình tạo ra một vòng lặp cho phép người dùng nhập vào các giá trị cho mảng. Hãy xuất kết quả mảng cùng với giá trị Count, và Capacity của mảng. Ta có thể thiết lập giá trị Capacity nhỏ hơn giá trị Count được không?
Viết chương trình tạo ra đối tượng Queue tên là myQueue. Khởi tạo myQueue có 5 giá trị ngẫu nhiên. Hãy thực hiện các bước sau, mỗi bước thực hiện phải xuất tình trạng của myQueue:
1. Lấy một giá trị ra.
2. Lấy tiếp một giá trị nữa.
3. Xem một giá trị ở đầu queue.
4. Đưa vào queue một giá trị.
Viết chương trình tạo đối tượng Stack tên là myStack. Khởi tạo myStack có 5 giá trị ngẫu nhiên. Hãy thực hiện các bước sau, mỗi bước thực hiện phải xuất tình trạng của myStack:
1. Lấy một giá trị ra.
2. Lấy tiếp một giá trị nữa.
3. Xem một giá trị ở đầu stack.
4. Đưa vào stack một giá trị.
Viết chương trình sử dụng kiểu dữ liệu từ điển để quản lý thông tin của một lớp học. Trong đó khóa là chuỗi mã số học viên còn giá trị là tên của học viên. Viết chương trình minh họa cho phép nhập vào 10 học viên, và cho phép người dùng tìm kiếm tên của học viên thông qua mã số học viên.
